Average performance analysis
Alexander Souza · 2006
The purpose of measures in algorithm theory is to distinguish between “good ” and “bad ” algorithms. The main drawback of classical worst-case analysis is that one single “bad ” instance decides the performance of an algorithm. Moreover, worst-case instances are often quite artificial and often do not represent a “realistic ” or “typical ” instance of a problem. In this thesis, we are concerned with an approach that tries to adress this issue: average performance analysis. Consider an optimisation problem and let Alg be an arbitrary (online) algorithm for it. An adversary Adv chooses the distribution D of the input instances out of a fixed class ∆adv of distributions. Let Opt be an optimal algorithm for the considered problem. Then, the average performance ratio apr of the algorithm Alg is defined by alg