arXiv preprint ·
Near-Optimal Online Metric Matching on $Δ$-ary HST
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In the online metric matching problem, we have $n$ servers with known locations in some metric space. Requests arrive one-by-one at certain locations, and upon arrival a request must be matched to a server that was not matched to a previous request. The goal is to minimize the matching cost. For randomized algorithms with an oblivious adversary, the best known competitive ratio is obtained by embedding the metric space into an HST, and then solving the problem in the setting where the metric space is defined by the HST. Bansal et al. (Algorithmica, 2014) introduced a framework for online metric matching where one develops an algorithm in a restricted reassignment model, and then transforms this into a true online algorithm. Using this framework, they obtained an expected competitive ratio of $O(\log n)$ for HSTs; this also gives the best known competitive ratio of $O(\log^2 n)$ for general metrics. In this paper, we revisit this framework with the aim of developing new algorithms. For HSTs where each node has at most $Δ$ children, we develop an algorithm via this framework with an expected competitive ratio of $O((\log\log Δ) \cdot \log Δ)$. In particular, this ratio is independent of $n$, the number of servers/requests. It is near-optimal, as the expected competitive ratio of any algorithm is $Ω(\log Δ)$.
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
Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable
Factorisability of Low Dimensional Non-Negative Integer Matrices
FPT Isomorphism Test for $F$-Free Tournaments
Backtracking Candidate Elimination: A One-Pass Algorithm for the Chip Testing Problem
On the Offline Version of the Time-Optimal k-Server Problem
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.