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 Ω(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.
