Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Bringmann, Karl
Panagiotou, Konstantinos

dblp
dblp

Not MPG Author(s):

Panagiotou, Konstantinos

Editor(s):

Czumaj, Artur
Mehlhorn, Kurt
Pitts, Andrew M.
Wattenhofer, Roger

dblp
dblp
dblp
dblp

Not MPII Editor(s):

Czumaj, Artur
Pitts, Andrew M.
Wattenhofer, Roger

BibTeX cite key*:

BringmannP12

Title, Booktitle

Title*:

Efficient Sampling Methods for Discrete Distributions

Booktitle*:

Automata, Languages, and Programming : 39th International Colloquium, ICALP 2012

Event, URLs

URL of the conference:

http://www2.warwick.ac.uk/fac/cross_fac/dimap/icalp2012/

URL for downloading the paper:


Event Address*:

Warwick, UK

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

9 July 2012

Event End Date:

13 July 2012

Publisher

Name*:

Springer

URL:

http://www.springer-ny.com/

Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

7391

Number:


Month:


Pages:

133-144

Year*:

2012

VG Wort Pages:


ISBN/ISSN:

978-3-642-31593-0

Sequence Number:


DOI:

10.1007/978-3-642-31594-7_12



Note, Abstract, ©


(LaTeX) Abstract:

We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities p_1,...,p_n. We consider the problem of sampling a subset, which includes the i-th event independently with probability p_i, and the problem of sampling from the distribution, where the i-th event has a probability proportional to p_i. For both problems we present on two different classes of inputs – sorted and general probabilities – efficient preprocessing algorithms that allow for asymptotically optimal querying, and prove almost matching lower bounds for their complexity.



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{BringmannP12,
AUTHOR = {Bringmann, Karl and Panagiotou, Konstantinos},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew M. and Wattenhofer, Roger},
TITLE = {Efficient Sampling Methods for Discrete Distributions},
BOOKTITLE = {Automata, Languages, and Programming : 39th International Colloquium, ICALP 2012},
PUBLISHER = {Springer},
YEAR = {2012},
VOLUME = {7391},
PAGES = {133--144},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Warwick, UK},
ISBN = {978-3-642-31593-0},
DOI = {10.1007/978-3-642-31594-7_12},
}


Entry last modified by Anja Becker, 01/29/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
12/13/2012 10:33:29 AM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Anja Becker
Karl Bringmann

Edit Dates
29.01.2013 12:48:33
29.01.2013 12:47:37
13.12.2012 10:33:29