arXiv preprint ·
A Potential Function Analysis of Double Coverage for the $k$-Taxi Problem on Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We provide potential function proofs of the competitive ratios of DoubleCoverage for the hard $k$-taxi problem on HSTs and general weighted trees of bounded depth. Buchbinder, Coester, and Naor (2023) obtained these ratios using time-reverse dual fitting and noted that they did not know a pure potential proof beyond $k=2$. We observe that the minimum matching distance between the online and offline taxi configurations can be expressed as an integral over the rooted tree of the absolute difference between their taxi counts below each point. This representation lets us analyse DoubleCoverage over short movement intervals and apply the resulting estimates to potentials that remain unchanged when both serving taxis are relocated from pickup to destination.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.