“Balls into Bins” — A Simple and Tight Analysis

Martin Raab, Angelika Steger

Type: Book-Chapter

Publication Date: 1998-01-01

Citations: 467

DOI: https://doi.org/10.1007/3-540-49543-6_13

View Publication

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	The Probability to Hit Every Bin with a Linear Number of Balls	2024	Stefan Walzer
+ PDF Chat	Tight Bounds for Repeated Balls-into-Bins	2022	Dimitrios Los Thomas Sauerwald
+	Tight Bounds for Repeated Balls-into-Bins	2022	Dimitrios Los Thomas Sauerwald
+	A Short Note on the Average Maximal Number of Balls in a Bin	2019	Marcus Michelen
+	A Short Note on the Average Maximal Number of Balls in a Bin	2019	Marcus Michelen
+ PDF Chat	A Generalization of Multiple Choice Balls-into-Bins: Tight Bounds	2016	Gahyun Park
+	A Short Note on the Average Maximal Number of Balls in a Bin.	2019	Marcus Michelen
+	Balls and Bins -- Simple Concentration Bounds	2022	Ernst Schulte-Geers Bo Waggoner
+	Balanced Allocations in Batches	2022	Dimitrios Los Thomas Sauerwald
+	A Quick Proof for the Volume of n-Balls	2001	Jean B. Lasserre
+	Balanced Allocations in Batches: Simplified and Generalized	2022	Dimitrios Los Thomas Sauerwald
+	On The Ballot Theorems	1997	Lajos Takács
+	Lower Bounds: Basic Ideas	2020	Tor Lattimore Csaba Szepesvári
+	Long-term balanced allocation via thinning	2021	Ohad N. Feldheim Ori Gurel-Gurevich Jiange Li
+ PDF Chat	Long-term balanced allocation via thinning	2024	Ohad N. Feldheim Ori Gurel-Gurevich Jiange Li
+	The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm	2014	P. Bertrand Christoph Lenzen
+	The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm	2014	P. Bertrand Christoph Lenzen
+	A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing	2010	Richard Beigel Bin Fu
+	A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing	2010	Richard Beigel Bin Fu
+	High-Probability Lower Bounds	2020	Tor Lattimore Csaba Szepesvári

Works That Cite This (144)

Action	Title	Year	Authors
+ PDF Chat	The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy	2021	Tommaso Cai Yichen Wang Linjun Zhang
+	Cliques in Hyperbolic Random Graphs	2017	Thomas Bläsius Tobias Friedrich Anton Krohmer
+ PDF Chat	Semi‐random graph process	2019	Omri Ben‐Eliezer Dan Hefetz Gal Kronenberg Olaf Parczyk Clara Shikhelman Miloš Stojaković
+	Balanced allocations	2000	Petra Berenbrink Artur Czumaj Angelika Steger Berthold Vöcking
+ PDF Chat	Eigenvalue Results for Large Scale Random Vandermonde Matrices With Unit Complex Entries	2011	Gabriel H. Tucci Philip Whiting
+	Load balancing of unit size tokens and expansion properties of graphs	2003	Robert Els Burkhard Monien
+	Semi-random graph process	2018	Omri Ben‐Eliezer Dan Hefetz Gal Kronenberg Olaf Parczyk Clara Shikhelman Miloš Stojaković
+	Almost sure Assouad-like Dimensions of Complementary sets	2019	I. Garcı́a Kathryn E. Hare Franklin Mendivil
+	Combinatorial Communication in the Locker Room	2020	Artur Czumaj George Kontogeorgiou Mike Paterson
+ PDF Chat	Simplified Witness Tree Arguments	2000	Thomas Schickinger Angelika Steger

Works Cited by This (0)

Action	Title	Year	Authors