ALCOMFT-TR-01-30

Michele Flammini and Gaia Nicosia
On Multicriteria Online Problems
Rome. Work package 4. March 2001.

Abstract: In this paper we consider multicriteria formulations of classical online problems in which an algorithm must simultaneously perform well with respect to two different cost measures. Every strategy for serving a sequence of requests is characterized by a pair of costs, and therefore there can be many different minimal or optimal incomparable solutions. The performance of the algorithm is compared with that of an adversary that serves the sequence selecting one of such optimal offline strategies according to a given selection function. We consider a parametric family of functions which includes all the possible selections. Then, starting from a simple general method that combines any multicriteria instance into a single-criterion one, we provide a universal multicriteria algorithm that can be applied to different online problems. In the multicriteria k-server formulation with two different edge weightings, for each function class, such a universal algorithm achieves competitive ratios that are only an O(log W) multiplicative factor away from the corresponding determined lower bounds, where W is the maximum ratio between the two weights associated to each edge. We then extend our results to more specific functions, for which optimal or nearly optimal competitive algorithms are obtained by exploiting more knowledge of the selection properties. Finally, we show how to apply our framework to other multicriteria online problems sharing similar properties.

Postscript file: ALCOMFT-TR-01-30.ps.gz (167 kb).