The Online k-Taxi Problem

We consider the online k-taxi problem, a generalization of the k-server problem, in which k taxis serve a sequence of requests in a metric space. A request consists of two points s and t, representing a passenger that wants to be carried by a taxi from s to t. The goal is to serve all requests while minimizing the total distance traveled by all taxis. The problem comes in two flavors, called the easy and the hard k-taxi problem: In the easy k-taxi problem, the cost is defined as the total distance traveled by the taxis; in the hard k-taxi problem, the cost is only the distance of empty runs. The hard k-taxi problem is substantially more difficult than the easy version with at least an exponential deterministic competitive ratio, Omega(2k), admitting a reduction from the layered graph traversal problem. In contrast, the easy k-taxi problem has exactly the same competitive ratio as the k-server problem. We focus mainly on the hard version. For hierarchically separated trees (HSTs), we present a memoryless randomized algorithm with competitive ratio 2k-1 against adaptive online adversaries and provide two matching lower bounds: for arbitrary algorithms against adaptive adversaries and for memoryless algorithms against oblivious adversaries. Due to well-known HST embedding techniques, the algorithm implies a randomized O(2klog n)-competitive algorithm for arbitrary n-point metrics. This is the first competitive algorithm for the hard k-taxi problem for general finite metric spaces and general k. For the special case of k=2, we obtain a precise answer of 9 for the competitive ratio in general metrics. With an algorithm based on growing, shrinking and shifting regions, we show that one can achieve a constant competitive ratio also for the hard 3-taxi problem on the line (abstracting the scheduling of three elevators).