Poly-logarithmic Competitiveness for the k-Taxi Problem

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 Ω(2 k ), showing that it is significantly harder than kserver. Randomized algorithms are known with competitiveness O(2 k log n) (by Coester and Koutsoupias), O(2 O( √ log ∆ log k) log ∆ n) (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 Ω(log 2 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.