ZIB

1

Unknown

Probabilistic alternatives for competitive analysis (2012)

Hiller, Benjamin ; Vredeveld, Tjark

add to mindlist on the mindlist

Publication Date: 2020-08-05

Description: In the last 20 years competitive analysis has become the main tool for analyzing the quality of online algorithms. Despite of this, competitive analysis has also been criticized: It sometimes cannot discriminate between algorithms that exhibit significantly different empirical behavior, or it even favors an algorithm that is worse from an empirical point of view. Therefore, there have been several approaches to circumvent these drawbacks. In this survey, we discuss probabilistic alternatives for competitive analysis.

Language: English

Type: reportzib , doc-type:preprint

Format: application/pdf

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

PDF

Overview

2

Unknown

Stochastic dominance analysis of Online Bin Coloring algorithms (2012)

Hiller, Benjamin ; Vredeveld, Tjark

add to mindlist on the mindlist

Details

Publication Date: 2020-08-05

Description: 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.

Language: English

Type: reportzib , doc-type:preprint

Format: application/pdf

Permalink