Skip to main content
Journal cover image

On balls and bins with deletions

Publication ,  Conference
Cole, R; Frieze, A; Maggs, BM; Mitzenmacher, M; Richa, AW; Sitaraman, R; Upfal, E
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 1998

We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and deletions are determined by an adversary before the process begins. We show that with high probability the load in any bin is O(log log n). In fact, this result follows from recent work by Cole et al. concerning a more difficult problem of routing in a butterfly network. The main contribution of this paper is to give a different proof of this bound, which follows the lines of the analysis of Azar, Broder, Karlin, and Upfal for the corresponding static load balancing problem. We also give a specialized (and hence simpler) version of the argument from the paper by Cole et al. for the balls and bins scenario. Finally, we provide an alternative analysis also based on the approach of Azar, Broder, Karlin, and Upfal for the special case where items are deleted according to their age. Although this analysis does not yield better bounds than our argument for the general case, it is interesting because it utilizes a two dimensional family of random variables in order to account for the age of the items. This technique may be of more general use.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540651420

Publication Date

January 1, 1998

Volume

1518

Start / End Page

145 / 158

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cole, R., Frieze, A., Maggs, B. M., Mitzenmacher, M., Richa, A. W., Sitaraman, R., & Upfal, E. (1998). On balls and bins with deletions. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 1518, pp. 145–158). https://doi.org/10.1007/3-540-49543-6_12
Cole, R., A. Frieze, B. M. Maggs, M. Mitzenmacher, A. W. Richa, R. Sitaraman, and E. Upfal. “On balls and bins with deletions.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1518:145–58, 1998. https://doi.org/10.1007/3-540-49543-6_12.
Cole R, Frieze A, Maggs BM, Mitzenmacher M, Richa AW, Sitaraman R, et al. On balls and bins with deletions. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1998. p. 145–58.
Cole, R., et al. “On balls and bins with deletions.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1518, 1998, pp. 145–58. Scopus, doi:10.1007/3-540-49543-6_12.
Cole R, Frieze A, Maggs BM, Mitzenmacher M, Richa AW, Sitaraman R, Upfal E. On balls and bins with deletions. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1998. p. 145–158.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540651420

Publication Date

January 1, 1998

Volume

1518

Start / End Page

145 / 158

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences