b'@inproceedings{BringmannP12,'b'\nTITLE = {Efficient Sampling Methods for Discrete Distributions},\nAUTHOR = {Bringmann, Karl and Panagiotou, Konstantinos},\nLANGUAGE = {eng},\nISSN = {0302-9743},\nISBN = {978-3-642-31593-0},\nDOI = {10.1007/978-3-642-31594-7_12},\nLOCALID = {Local-ID: 76C613922FECC644C1257AD300348137-BringmannP12},\nPUBLISHER = {Springer},\nYEAR = {2012},\nDATE = {2012},\nABSTRACT = {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 {\\diamond} sorted and general probabilities {\\diamond} efficient preprocessing algorithms that allow for asymptotically optimal querying, and prove almost matching lower bounds for their complexity.},\nBOOKTITLE = {Automata, Languages, and Programming (ICALP 2012)},\nEDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew M. and Wattenhofer, Roger},\nPAGES = {133--144},\nSERIES = {Lecture Notes in Computer Science},\nVOLUME = {7391},\nADDRESS = {Warwick, UK},\n}\n'