Poly-logarithmic Competitiveness for the k-Taxi Problem

Anupam Gupta, Amit Kumar, Debmalya Panigrahi

Research output: Contribution to conferencePaperpeer-review


The online k-taxi problem generalizes the k-server problem, requiring servers to move between source-sink pairs in an n-point metric space, and the cost is the overhead incurred. In the deterministic setting, the problem has a lower bound on the competitiveness of Ω(2k), showing that it is significantly harder than kserver. Randomized algorithms are known with competitiveness O(2k log n) (by Coester and Koutsoupias), (Equation presented) (by Buchbinder, Coester and Naor), where ∆ is the aspect ratio of the n-point metric space), and O((n log k)2 log n) (by Bubeck, Buchbinder, Coester, and Sellke). The best lower bound known is Ω(log2 k) which is inherited from the k-server problem, obtained in a recent breakthrough by Bubeck, Coester, and Rabani, showing a large gap in our understanding of problems that go slightly beyond the metrical task system framework. An open question left by these works was whether there is a randomized algorithm for the the k-taxi problem with a competitive ratio that is poly-logarithmic in all the parameters. We answer this question in the affirmative in this paper. For our work, we give a covering relaxation for k-taxi on HSTs, which is obtained from the (non-covering) min-cost flow formulation of the problem. The constraints of our LP have compositionality properties that we use to develop a hierarchical primal-dual algorithm defined on the subtrees of the HST.

Original languageEnglish (US)
Number of pages27
StatePublished - 2024
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: Jan 7 2024Jan 10 2024


Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Poly-logarithmic Competitiveness for the k-Taxi Problem'. Together they form a unique fingerprint.

Cite this