The online 𝑘-taxi problem

Conference item

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, Ω(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(2klogn)-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).

Authors: Coester, C; Koutsoupias, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
• Journal: Symposium on the Theory of Computing (STOC) More from this journal
• Pages: 1136-1147
• Publication date: 2019-06-23
• Acceptance date: 2019-02-08
• DOI: 10.1145/3313276.3316370
• ISBN: 9781450367059
• Keywords: k-server; online algorithm; competitive analysis