arXiv preprint ·
A Better-than-$2$ Approximation for $k$-Median Part II: Stable Instances
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We consider the $k$-median problem on general metric spaces, subject to the condition that the instances are $β$-stable (i.e., the optimal solution using $k-1$ centers has a cost at least $(1+β)$ times that of the optimal solution with $k$ centers). We give a $(1.89+ε)$-approximation algorithm for such instances running in time $\exp(1/(β\times \mathrm{poly}(ε)))\cdot \mathrm{poly}_ε(n)$. In particular, for $β=\mathrm{poly}(ε)/\log n$ and $ε$ a tiny constant, this is a polynomial-time algorithm. This improves on previous work showing a $(2 + ε)$-approximation algorithm with similar running time [CGL+25]. Combined with the pseudo-approximation algorithm in our companion work, this results in a better-than-$2$ approximation algorithm for general $k$-median instances. Our main technical contribution is a novel nuanced analysis of local search that allows us to isolate a subset of clients on which we lose essentially nothing compared to the optimal solution, while losing an approximation factor of $3$ on the rest of the clients. We complement this with an algorithm based on sampling and partial enumeration, achieving a better-than-$2$ approximation on the rest of the clients. Trading off these two algorithms yields our final approximation.
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
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Improved Combinatorial Auctions with and without Samples
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Stochastic Weighted Caching with Per-Request Predictions
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.