The Online k-Taxi Problem
share
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 traveled by taxis while not carrying a passenger, i.e., the distance from s to t is excluded from the cost. The hard k-taxi problem is substantially more difficult than the easy version with at least an exponential deterministic competitive ratio, Ω(2^k), admitting a reduction from the layered width-k graph traversal problem. In contrast, the easy k-taxi problem has exactly the same competitive ratio as the k-server problem. For the hard k-taxi problem on hierarchically separated trees (HSTs), we present a memoryless randomized algorithm with competitive ratio 2^k-1 against adaptive online adversaries and provide a matching lower bound. Due to well-known HST embedding techniques, this yields a randomized O(2^k n)-competitive algorithm for arbitrary n-point metric spaces. 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 on general metric spaces.
READ FULL TEXT