Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 15 von 186
Zurück zur Trefferliste

Stochastic dominance analysis of Online Bin Coloring algorithms

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-16502
  • This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than 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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Benjamin HillerORCiD, Tjark Vredeveld
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:online algorithms, stochastic dominance, algorithm analysis, Markov chains
MSC-Klassifikation:60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Datum der Erstveröffentlichung:15.11.2012
Schriftenreihe (Bandnummer):ZIB-Report (12-42)
ISSN:1438-0064
Lizenz (Deutsch):License LogoCreative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.