Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison

Please always quote using this URN: urn:nbn:de:0297-zib-10726
  • This paper proposes a new method for probabilistic analysis of online algorithms that is based on the notion of stochastic dominance. We develop the method for the Online Bin Coloring problem introduced by Krumke et al. Using methods for the stochastic comparison of Markov chains we establish the strong result that the performance of the online algorithm GreedyFit is stochastically dominated by the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Benjamin HillerORCiD, Tjark Vredeveld
Document Type:ZIB-Report
Tag:Markov-Ketten; Online-Algorithmen; Probabilistische Analyse; Stochastische Dominanz
Markov chains; online algorithms; probabilistic analysis; stochastic dominance
Date of first Publication:2008/04/21
Series (Serial Number):ZIB-Report (08-18)
Published in:Appeared in: Proceedings of the 16th Annual European Symposium on Algorithms, ESA 2008. Springer 2008. Lecture Notes in Computer Science, 5193, pp. 528-539
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.