On the bicriteria k-server problem

In this article 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 adversary is assumed to choose from one of these minimal strategies and the performance of the algorithm is measured with respect to the costs the adversary pays servicing the sequence according to its determined choice of strategy. We consider a parametric family of functions which includes all the possible selections for such strategies. 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 two specific functions, for which 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.