{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:16Z","timestamp":1740109276038,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,3,17]],"date-time":"2016-03-17T00:00:00Z","timestamp":1458172800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0141-z","type":"journal-article","created":{"date-parts":[[2016,3,18]],"date-time":"2016-03-18T13:27:27Z","timestamp":1458307647000},"page":"1159-1193","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Generalization of Multiple Choice Balls-into-Bins: Tight Bounds"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8415-8512","authenticated-orcid":false,"given":"Gahyun","family":"Park","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,17]]},"reference":[{"key":"141_CR1","doi-asserted-by":"crossref","unstructured":"Adler, M., Chakrabarti, S., Mitzenmacher, M., Rasmussen, L.: Parallel randomized load balancing. In: Symposium on Theory of Computing. ACM, pp. 119\u2013130 (1995)","DOI":"10.1145\/225058.225131"},{"issue":"1","key":"141_CR2","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Yossi Azar","year":"1999","unstructured":"Azar, Yossi, Broder, Andrei Z., Karlin, Anna R., Upfal, Eli: Balanced allocations. SIAM J. Comput. 29(1), 180\u2013200 (1999)","journal-title":"SIAM J. Comput."},{"key":"141_CR3","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Czumaj, A., Englert, M., Friedetzky, T., Nagel, L.: Multiple-choice balanced allocation in (almost) parallel. In: Proceedings of the International Workshop on Randomization and Computation (RANDOM 2012), pp. 411\u2013422 (2012)","DOI":"10.1007\/978-3-642-32512-0_35"},{"key":"141_CR4","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Brinkmann, A., Friedetzky, T., Meister, D., Nagel Dirk, L.: Distributing storage in cloud environments. In: Proceedings of High-Performance Grid and Cloud Computing Workshop (workshop of IPDPS) (2013)","DOI":"10.1109\/IPDPSW.2013.148"},{"issue":"6","key":"141_CR5","doi-asserted-by":"crossref","first-page":"1350","DOI":"10.1137\/S009753970444435X","volume":"35","author":"P Berenbrink","year":"2006","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: the heavily loaded case. SIAM J. Comput. 35(6), 1350\u20131385 (2006)","journal-title":"SIAM J. Comput."},{"key":"141_CR6","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Khodamoradi, K., Sauerwald, T., Stauffer, A.: Balls-into-bins with nearly optimal load distribution. In: Proceedings of the 25th Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 326\u2013335 (2013)","DOI":"10.1145\/2486159.2486191"},{"issue":"4","key":"141_CR7","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1002\/rsa.1011","volume":"18","author":"A Czumaj","year":"2001","unstructured":"Czumaj, A., Stemann, V.: Randomized allocation processes. Random Struct. Algorithms 18(4), 297\u2013331 (2001)","journal-title":"Random Struct. Algorithms"},{"key":"141_CR8","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D Dubhashi","year":"1996","unstructured":"Dubhashi, D., Ranjan, D.: Balls and bins: a study in negative dependence. Random struct. Algorithms 13, 99\u2013124 (1996)","journal-title":"Random struct. Algorithms"},{"key":"141_CR9","unstructured":"Godfrey, P.B.: Balls and bins with structure: balanced allocations on hypergraphs. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 511\u2013517 (2008)"},{"key":"141_CR10","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Tight bounds for parallel randomized load balancing: extended abstract. In: STOC \u201911, pp. 11\u201320 (2011)","DOI":"10.1145\/1993636.1993639"},{"key":"141_CR11","unstructured":"Mitzenmacher, M.:The Power of Two Choices in Randomized Load Balancing. Thesis, University of California, Berkeley (1996)"},{"key":"141_CR12","doi-asserted-by":"crossref","unstructured":"Ousterhout, K., Wendell, P., Zaharia, M., Stoica, I.: Sparrow: distributed, low latency scheduling. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP \u201913, ACM, pp. 69\u201384, New York, USA (2013)","DOI":"10.1145\/2517349.2522716"},{"key":"141_CR13","doi-asserted-by":"crossref","unstructured":"Park, G.: Brief announcement: a generalization of multiple choice balls-into-bins. In: PODC \u201911, pp. 297\u2013298 (2011)","DOI":"10.1145\/1993806.1993862"},{"key":"141_CR14","doi-asserted-by":"crossref","unstructured":"Peres, Y., Talwar, K., Wieder, U.: The $$(1+\\beta )$$ ( 1 + \u03b2 ) -choice process and weighted balls into bins. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1613\u20131619 (2010)","DOI":"10.1137\/1.9781611973075.131"},{"key":"141_CR15","doi-asserted-by":"crossref","unstructured":"Raab, M., Steger, A.: Balls into bins\u2014a simple and tight analysis. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) Randomization and Approximation Techniques in Computer Science, vol. 1518, pp. 159\u2013170. Springer, Heidelberg (1998)","DOI":"10.1007\/3-540-49543-6_13"},{"key":"141_CR16","doi-asserted-by":"crossref","unstructured":"Stemann, V.: Parallel balanced allocations. In: Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA \u201996, ACM, pp. 261\u2013269, New York, USA (1996)","DOI":"10.1145\/237502.237565"},{"key":"141_CR17","doi-asserted-by":"crossref","unstructured":"Talwar, K., Wieder, U.: Balanced allocations: the weighted case. In: Proceedings of the thirty-ninth annual ACM Symposium on Theory of Computing, STOC \u201907, pp. 256\u2013265 (2007)","DOI":"10.1145\/1250790.1250829"},{"key":"141_CR18","doi-asserted-by":"crossref","unstructured":"Talwar, K., Wieder, U.: Balanced allocations: a simple proof for the heavily loaded case. In: Proceedings of Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, 8\u201311 July 2014, Part I, pp. 979\u2013990 (2014)","DOI":"10.1007\/978-3-662-43948-7_81"},{"issue":"4","key":"141_CR19","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1145\/792538.792546","volume":"50","author":"B V\u00f6cking","year":"2003","unstructured":"V\u00f6cking, B.: How asymmetry helps load balancing. J. ACM 50(4), 568\u2013589 (2003)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0141-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0141-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0141-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0141-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T14:04:39Z","timestamp":1567692279000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0141-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,17]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["141"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0141-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,3,17]]}}}