Relative Worst-Order Analysis: A Survey

Joan Boyar, Lene Monrad Favrholdt, Kim Skak Larsen*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

85 Downloads (Pure)


The standard measure for the quality of online algorithms is the competitive ratio. This measure is generally applicable, and for some problems it works well, but for others it fails to distinguish between algorithms that have very different performance. Thus, ever since its introduction, researchers have worked on improving the measure, defining variants, or defining measures based on other concepts to improve on the situation. Relative worst-order analysis (RWOA) is one of the most thoroughly tested such proposals. With RWOA, many separations of algorithms not obtainable with competitive analysis have been found.

In RWOA, two algorithms are compared directly, rather than indirectly as is done in competitive analysis, where both algorithms are compared separately to an optimal offline algorithm. If, up to permutations of the request sequences, one algorithm is always at least as good and sometimes better than another, then the first algorithm is deemed the better algorithm by RWOA.
We survey the most important results obtained with this technique and compare it with other quality measures. The survey includes a quite complete set of references.
Original languageEnglish
Article number8
JournalACM Computing Surveys
Issue number1
Number of pages21
Publication statusPublished - Jan 2021


Dive into the research topics of 'Relative Worst-Order Analysis: A Survey'. Together they form a unique fingerprint.

Cite this