A Survey of Performance Measures for On-line Algorithms
[.ps]
[.pdf]
Abstract
The competitive ratio is the most common metric in on-line algorithm analysis. The growth and strength of the field is due in no small part to the effectiveness of this measure in the course of practical analysis. On the other hand, there are known applications in which the competitive ratio produces somewhat unsatisfactory results. In some cases it results in unrealistically pessimistic measures, in others it fails to distinguish between algorithms that have vastly differing performance under any practical characterization. In addition, there are situations in which we might simply desire a different measure than that provided by the competitive ratio. Because of this various alternatives to the competitive ratio have been proposed in the literature. In this paper we survey several of those alternatives, highlight their distinctive properties and discuss their benefits and drawbacks.
Bibtex Entry
