| Alan Frieze y (2007) | |||||||||||||
Abstract | |||||||||||||
| We consider the problem of extending the analysis of balls and bins processes 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. Most previous work has focused on the less realistic case of random deletions. We also provide an alternative analysis 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. 1 | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||