Competitive analysis of k-server variants and metrical task systems

In the online k-server problem, an algorithm controls k mobile servers in a metric space. One by one, requests arrive at points of the space, and the algorithm must serve each request by selecting a server to visit it. The goal is to minimize the total distance traveled by all servers. In the framework of competitive analysis, we study two variants of the k-server problem, the infinite server problem and the k-taxi problem, and the more general metrical task systems problem. The infinite server problem is the variant of the k-server problem where the number of servers is infinite, initially all starting at the same point. We obtain a surprisingly tight connection between the infinite server problem and the resource augmentation version of the k-server problem. Using this connection, we also improve the known lower bounds for the resource augmented k-server problem. The k-taxi problem generalizes the k-server problem in that a request consists not of one point, but two points s and t, representing the start and destination of a taxi request. To serve such a request, a server (taxi) must move first to s and then to t. This problem becomes particularly difficult when the cost is defined as the distance of empty runs only. Indeed, we show an exponential gap between the competitive ratio of the k-taxi problem and that of the k-server problem. A main positive result is an O(2k log n)-competitive algorithm for arbitrary n-point metrics. Metrical task systems are a general framework subsuming many other online problems, including the k-server problem. Here, the algorithm suffers two kinds of costs, movement and service costs. For HST metrics, using an entropy regularization approach, we obtain tight bounds on the refined guarantees, i.e., movement and service costs are simultaneously optimally competitive against the optimal total cost. This also improves the refined guarantees for general metrics.