2011 | OriginalPaper | Buchkapitel
Faster Coupon Collecting via Replication with Applications in Gossiping
verfasst von : Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Lars Nagel, Thomas Sauerwald
Erschienen in: Mathematical Foundations of Computer Science 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider an extension of the well-known
coupon collecting
(CC) problem. In our model we have a player who is allowed to deterministically select one box per time step. The player plays against a random sequence of box choices
r
1
,
r
2
,… In each step, the contents of both boxes are merged.
The goal of the player is to collect all coupons in one box (the standard model), or to have a copy of each coupon in
all
boxes. We consider three information models, depending on the knowledge of the random choices that the player has before he has to fix his deterministic choices: (i) full prior knowledge of the whole random sequence; (ii) knowledge of the random sequence up to the previous step (but not the current or any subsequent step); (iii) all decisions must be made in advance without any knowledge of the random sequence.
Our main results are lower and asymptotically matching constructive upper bounds for all three models. We also show that network gossiping (similar in spirit to all-in-all CC) is asymptotically no harder than collecting coupons.