{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:15:56Z","timestamp":1780766156994,"version":"3.54.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T00:00:00Z","timestamp":1472428800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00453-016-0205-0","type":"journal-article","created":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T13:55:24Z","timestamp":1472478924000},"page":"484-508","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Efficient Sampling Methods for Discrete Distributions"],"prefix":"10.1007","volume":"79","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","published-online":{"date-parts":[[2016,8,29]]},"reference":[{"key":"205_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. Elsevier Publishing Company, London (1975)"},{"key":"205_CR2","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Friedrich, T.: Exact and efficient generation of geometric random variates and random graphs. In: Proceedings of 40th International Colloquium on Automata, Languages, and Programming (ICALP\u201913), pp. 267\u2013278 (2013)","DOI":"10.1007\/978-3-642-39206-1_23"},{"key":"205_CR3","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Green\u00a0Larsen, K.: Succinct sampling from discrete distributions. In Proceedings of 45th Annual ACM Symposium on Theory of Computing (STOC\u201913), pp. 775\u2013782 (2013)","DOI":"10.1145\/2488608.2488707"},{"issue":"1","key":"205_CR4","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1080\/15427951.2004.10129081","volume":"1","author":"Fan Chung","year":"2004","unstructured":"Chung, Fan, Linyuan, Lu: The average distance in a random graph with given expected degrees. Internet Math. 1(1), 91\u2013113 (2004)","journal-title":"Internet Math."},{"key":"205_CR5","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":"205_CR6","doi-asserted-by":"crossref","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. J. Algorithms 7(4), 463\u2013488 (1986)","journal-title":"J. Algorithms"},{"key":"205_CR7","doi-asserted-by":"crossref","unstructured":"Hagerup, T., Mehlhorn, K. and Munro, I.: Maintaining discrete probability distributions optimally. In: Proceedings of 20th International Colloquium on Automata, Languages, and Programming (ICALP \u201993), pp. 253\u2013264 (1993)","DOI":"10.1007\/3-540-56939-1_77"},{"key":"205_CR8","volume-title":"The Art of Computer Programming, Vol. 2: Seminumerical Algorithms","author":"DE Knuth","year":"2009","unstructured":"Knuth, D.E.: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd edn. Addison-Wesley Publishing Company, Boston (2009)","edition":"3"},{"key":"205_CR9","unstructured":"Knuth, D.E., Yao, A.C.: The complexity of nonuniform random number generation. In: Traub, J.F. (ed.) Algorithms and Complexity: New Directions and Recent Results, Proceedings of a Symposium, pp. 357\u2013428. Carnegie-Mellon University, Computer Science Department, Academic Press, New York, NY (1976)"},{"issue":"4","key":"205_CR10","doi-asserted-by":"crossref","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 Comput Syst 36(4), 329\u2013358 (2003)","journal-title":"Theory Comput Syst"},{"key":"205_CR11","doi-asserted-by":"crossref","unstructured":"Miller, J.C., Hagberg, A.A.: Efficient generation of networks with given expected degrees. In: Proceedings of 8th International Workshop Algorithms and Models for the Web Graph (WAW\u201911), pp. 115\u2013126 (2011)","DOI":"10.1007\/978-3-642-21286-4_10"},{"issue":"1A","key":"205_CR12","doi-asserted-by":"crossref","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. Ann. Appl. Probab. 15(1A), 93\u2013115 (2005)","journal-title":"Ann. Appl. Probab."},{"key":"205_CR13","volume-title":"Computational Geometry. Texts and Monographs in Computer Science","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry. Texts and Monographs in Computer Science. Springer, New York (1985)"},{"key":"205_CR14","unstructured":"P\u0103tra\u015fcu, M.: WebDiarios de Motocicleta, Sampling a discrete distribution. \n                        http:\/\/infoweekly.blogspot.com\/2011\/09\/sampling-discrete-distribution.html\n                        \n                     (2011)"},{"key":"205_CR15","doi-asserted-by":"crossref","unstructured":"Tsai, M.-T., Wang, D.-W., Liau, C.-J., Hsu, T.-S.: Heterogeneous subset sampling. In: Proceedings of 16th Annual International Computing and Combinatorics Conference (COCOON \u201910), pp. 500\u2013509 (2010)","DOI":"10.1007\/978-3-642-14031-0_53"},{"key":"205_CR16","doi-asserted-by":"crossref","unstructured":"Vitter, J.S.: Random sampling with a reservoir. ACM Trans. Math. Softw. 11(1), 37\u201357 (1985)","DOI":"10.1145\/3147.3165"},{"key":"205_CR17","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1049\/el:19740097","volume":"10","author":"AJ Walker","year":"1974","unstructured":"Walker, A.J.: New fast method for generating discrete random numbers with arbitrary distributions. Electron. Lett. 10, 127\u2013128 (1974)","journal-title":"Electron. Lett."},{"key":"205_CR18","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Context-free grammars and random number generation. In: Combinatorial Algorithms on Words 12, 357\u2013361 (1985)","DOI":"10.1007\/978-3-642-82456-2_25"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0205-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0205-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0205-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T18:37:31Z","timestamp":1501526251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0205-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,29]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["205"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0205-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,29]]}}}