2015 | OriginalPaper | Buchkapitel
Competitive Analysis for Multi-objective Online Algorithms
Autoren: Morten Tiedemann, Jonas Ide, Anita Schöbel
Verlag: Springer International Publishing
So far, the concept of competitive analysis for online problems is in general applied to single-objective online problems. However, many online problems can be extended to multi-objective online problems in a natural way, but a uniform theory for the analysis of these problems is not provided in the literature. We expand the concept of competitive analysis to multi-objective online problems and achieve a consistent framework for the analysis of multi-objective online problems. Furthermore, we analyze the multi-objective time series search problem and present deterministic algorithms with best possible competitive ratios.
