Relative Worst-order Analysis: A Survey

摘要: The standard measure for the quality of online algorithms is competitive ratio. This generally applicable, and some problems it works well, but others fails to distinguish between that have very different performance. Thus, ever since its introduction, researchers worked on improving measure, defining variants, or measures based other concepts improve situation. Relative worst-order analysis (RWOA) one most thoroughly tested such proposals. With RWOA, many separations not obtainable with been found. In two are compared directly, rather than indirectly as done in analysis, where both separately an optimal offline algorithm. If, up permutations request sequences, algorithm always at least good sometimes better another, then first deemed by RWOA. We survey important results obtained this technique compare measures. includes a quite complete set references.