Abstract
Balls-into-bins games describe in an abstract setting several multiple-choice scenarios, and allow for a systematic and unified theoretical treatment. In the process that we consider, there are n bins, initially empty, and \(m = \lfloor cn\rfloor \) balls. Each ball chooses independently and uniformly at random k ≥ 3 bins. We are looking for an allocation such that each ball is placed into one of its chosen bins and no bin has load greater than 1. How quickly can we find such an allocation? We present a simple and novel algorithm that finds such an allocation (if it exists) and runs in linear time with high probability.
Our algorithm finds applications in finding perfect matchings in a special class of sparse random bipartite graphs, orientation of random hypergraphs, load balancing and hashing.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Azar, Y., Broder, A., Karlin, A., Upfal, E.: Balanced allocations. SIAM Journal on Computing 29(1), 180–200 (1999)
Cain, J.A., Sanders, P., Wormald, N.: The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In: ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 469–476 (2007)
Fernholz, D., Ramachandran, V.: The k-orientability thresholds for gn, p. In: ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 459–468 (2007)
Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.: Space efficient hash tables with worst case constant access time. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 271–282. Springer, Heidelberg (2003)
Fountoulakis, N., Khosla, M., Panagiotou, K.: The multiple-orientability thresholds for random hypergraphs. In: ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 1222–1236 (2011)
Fountoulakis, N., Panagiotou, K.: Sharp load thresholds for cuckoo hashing. Random Structures & Algorithms 41(3), 306–333 (2012)
Fountoulakis, N., Panagiotou, K., Steger, A.: On the insertion time of cuckoo hashing. CoRR, abs/1006.1231 (2010)
Frieze, A., Melsted, P.: Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables. Random Structures & Algorithms 41(3), 334–364 (2012)
Frieze, A., Melsted, P., Mitzenmacher, M.: An analysis of random-walk cuckoo hashing. SIAM Journal on Computing 40(2), 291–308 (2011)
Galassi, M., Davies, J., Theiler, J., Gough, B., Jungman, G., Booth, M., Rossi, F.: Gnu scientific library reference manual (2003), http://www.gnu.org/software/gsl
Lelarge, M.: A new approach to the orientation of random hypergraphs. In: ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 251–264 (2012)
Mitzenmacher, M., Richa, A., Sitaraman, R.: The power of two random choices: A survey of techniques and results. In: Handbook of Randomized Algorithms, pp. 255–312 (2000)
Motwani, R.: Average-case analysis of algorithms for matchings and related problems. J. ACM 41(6), 1329–1356 (1994)
Pagh, R., Rodler, F.F.: Cuckoo hashing. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 121–133. Springer, Heidelberg (2001)
Sanders, P., Egner, S., Korst, J.: Fast concurrent access to parallel disks. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 849–858 (1999)
Schlegel, B., Gemulla, R., Lehner, W.: Fast integer compression using simd instructions. In: Workshop on Data Management on New Hardware, DaMoN 2010, pp. 34–40. ACM (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khosla, M. (2013). Balls into Bins Made Faster. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_51
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)