Competitive algorithms for the bicriteria k-server problem

In this paper we consider the bicriteria formulation of the well-known online k-server problem where the cost of moving k servers between given locations is evaluated simultaneously with respect to two different metrics. Every strategy for serving a sequence of requests is thus characterized by a pair of costs, and an online algorithm is said to be (c1, c2)-competitive in the strong sense if it is c1-competitive with respect to the first metric and c2-competitive with respect to the second one. We first prove a lower bound on c1 and c2 that holds for any online bicriteria algorithm for the problem.We then propose an algorithm achieving asymptotically optimal tradeoffs between the two competitive ratios. Finally, we show how to further decrease the competitive ratios when the two metrics are induced by the distances in a complete graph and in a path, respectively, obtaining optimal results for particular cases.