## Abstract

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

Original language | English (US) |
---|---|

Pages | 4220-4246 |

Number of pages | 27 |

DOIs | |

State | Published - 2024 |

Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: Jan 7 2024 → Jan 10 2024 |

### Conference

Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|

Country/Territory | United States |

City | Alexandria |

Period | 1/7/24 → 1/10/24 |

## ASJC Scopus subject areas

- Software
- General Mathematics