The Weighted Coupon Collector’s Problem and Applications

DOI10.1007/978-3-642-02882-3_45MaRDI QIDQ5323093zbMATH OpenOpenAlexFDO

Authors Petra Berenbrink, Thomas Sauerwald

Publication date 23 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02882-3_45

Mathematics Subject Classification ID

Random walks on graphs (05C81) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Optimality results for coupon collection
• New results on a generalized coupon collector problem using Markov chains
• Optimization results for a generalized coupon collector problem
• Collecting coupons on trees, and the cover time of random walks
• A generalized coupon collector problem

Cites work

• A tight lower bound on the cover time for random walks on graphs
• A tight upper bound on the cover time for random walks on graphs
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Elementary Probability
• Extremal cover times for random walks on trees
• scientific article; zbMATH DE number 1958330 (Why is no real title available?)
• On the Runtime and Robustness of Randomized Broadcasting
• Randomized broadcast in networks
• The coupon-collector's problem revisited

Cited in

(6)

• Coupon collector's problems with statistical applications to rankings
• The weighted words collector
• Faster coupon collecting via replication with applications in gossiping
• Two Poisson limit theorems for the coupon collector's problem with group drawings
• Computing absorbing times via fluid approximations
• The number of K-tons in the coupon collector problem

This page was built for publication: The Weighted Coupon Collector’s Problem and Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5323093)