返回Google圖書搜尋

Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison

出版	METEOR, Maastricht research school of Economics of TEchnology and ORganizations, 2008
URL	http://books.google.com.hk/books?id=bEazSgAACAAJ&hl=&source=gbs_api

註釋Abstract: "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 in [15]. 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."