TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Stochastic dominance analysis of Online Bin Coloring algorithms N2 - 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. T3 - ZIB-Report - 12-42 KW - online algorithms, stochastic dominance, algorithm analysis, Markov chains Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16502 SN - 1438-0064 ER -