{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T06:14:03Z","timestamp":1784182443259,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642315930","type":"print"},{"value":"9783642315947","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_12","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"133-144","source":"Crossref","is-referenced-by-count":18,"title":["Efficient Sampling Methods for Discrete Distributions"],"prefix":"10.1007","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Konstantinos","family":"Panagiotou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"12_CR1","volume-title":"The computational complexity of algebraic and numeric problems","author":"A. Borodin","year":"1975","unstructured":"Borodin, A., Munro, I.: The computational complexity of algebraic and numeric problems. American Elsevier Publishing Co., Inc., New York (1975)"},{"key":"12_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Nonuniform random variate generation","author":"L. Devroye","year":"1986","unstructured":"Devroye, L.: Nonuniform random variate generation. Springer, New York (1986)"},{"issue":"4","key":"12_CR3","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/0196-6774(86)90014-3","volume":"7","author":"P. Flajolet","year":"1986","unstructured":"Flajolet, P., Saheb, N.: The complexity of generating an exponentially distributed variate. Journal of Algorithms\u00a07(4), 463\u2013488 (1986)","journal-title":"Journal of Algorithms"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/3-540-56939-1_77","volume-title":"Automata, Languages and Programming","author":"T. Hagerup","year":"1993","unstructured":"Hagerup, T., Mehlhorn, K., Munro, J.I.: Maintaining Discrete Probability Distributions Optimally. In: Lingas, A., Carlsson, S., Karlsson, R. (eds.) ICALP 1993. LNCS, vol.\u00a0700, pp. 253\u2013264. Springer, Heidelberg (1993)"},{"key":"12_CR5","volume-title":"The Art of Computer Programming. Seminumerical Algorithms","author":"D.E. Knuth","year":"2009","unstructured":"Knuth, D.E.: The Art of Computer Programming. Seminumerical Algorithms, 3rd edn., vol.\u00a02. Addison-Wesley Publishing Co, Reading (2009)","edition":"3"},{"key":"12_CR6","first-page":"357","volume-title":"Algorithms and Complexity (Proc. Sympos.)","author":"D.E. Knuth","year":"1976","unstructured":"Knuth, D.E., Yao, A.C.: The complexity of nonuniform random number generation. In: Algorithms and Complexity (Proc. Sympos.), pp. 357\u2013428. Carnegie-Mellon Univ., Pittsburgh (1976)"},{"issue":"4","key":"12_CR7","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s00224-003-1078-6","volume":"36","author":"Y. Matias","year":"2003","unstructured":"Matias, Y., Vitter, J.S., Ni, W.C.: Dynamic generation of discrete random variates. Theory of Computing Systems\u00a036(4), 329\u2013358 (2003)","journal-title":"Theory of Computing Systems"},{"issue":"1A","key":"12_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1214\/105051604000000549","volume":"15","author":"\u015e. Nacu","year":"2005","unstructured":"Nacu, \u015e., Peres, Y.: Fast simulation of new coins from old. The Annals of Applied Probability\u00a015(1A), 93\u2013115 (2005)","journal-title":"The Annals of Applied Probability"},{"key":"12_CR9","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry. Texts and Monographs in Computer Science. Springer, New York (1985)"},{"key":"12_CR10","unstructured":"P\u0103tra\u015fcu, M.: Webdiarios de motocicleta, sampling a discrete distribution (2011), \n                    \n                      infoweekly.blogspot.com\/2011\/09\/sampling-discrete-distribution.html"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-642-14031-0_53","volume-title":"Computing and Combinatorics","author":"M.-T. Tsai","year":"2010","unstructured":"Tsai, M.-T., Wang, D.-W., Liau, C.-J., Hsu, T.-s.: Heterogeneous Subset Sampling. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol.\u00a06196, pp. 500\u2013509. Springer, Heidelberg (2010)"},{"key":"12_CR12","unstructured":"Tsai, M.T., Wang, D.W., Liau, C.J., Hsu, T.S.: Heterogeneous subset sampling (submitted for publication, 2012)"},{"issue":"1","key":"12_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3147.3165","volume":"11","author":"J.S. Vitter","year":"1985","unstructured":"Vitter, J.S.: Random sampling with a reservoir. ACM Trans. Math. Softw.\u00a011(1), 37\u201357 (1985)","journal-title":"ACM Trans. Math. Softw."},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1049\/el:19740097","volume":"10","author":"A.J. Walker","year":"1974","unstructured":"Walker, A.J.: New fast method for generating discrete random numbers with arbitrary distributions. Electronic Letters\u00a010, 127\u2013128 (1974)","journal-title":"Electronic Letters"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Context-free grammars and random number generation. In: Combinatorial algorithms on words (Maratea, 1984), vol.\u00a012, pp. 357\u2013361. Springer (1985)","DOI":"10.1007\/978-3-642-82456-2_25"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:14:48Z","timestamp":1620130488000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}