Source-linked AI summary
Approximating $k$-Median via Pseudo-Approximation
Shi Li, Ola Svensson
TL;DR
The paper studies how to improve k-median approximation despite its hard limit of k opened facilities. It reduces ordinary approximation to pseudo-approximation with a constant number of extra facilities and develops such an algorithm, improving on the previous 3+ϵ guarantee. The approach also raises an open question about the remaining gap between solutions with extra facilities and the k-facility LP value.
Problem
k-median's hard constraint of opening at most k facilities limits approximation progress, while prior pseudo-approximations required k+Ω(k) facilities.
Method
The paper reduces pseudo-approximation to ordinary approximation and constructs a bi-point-solution-based algorithm opening k+O(1/ϵ) facilities.
Results
The approach improves the previous 3+ϵ approximation guarantee, while its pseudo-approximation opens k+O(1/ϵ) facilities.
Takeaways & Limitations
Opening k+O(1) facilities can be compatible with an approximation algorithm that ultimately opens only k facilities.
Takeaways & Limitations
The maximum ratio between the optimum with k+O(1) facilities and the k-facility LP value remains an open question; hardness implies an integrality gap of at least 1+2/e even with k+o(k) facilities.
Abstract
from arXiv · showhide
We present a novel approximation algorithm for $k$-median that achieves an approximation guarantee of $1+\sqrt{3}+ε$, improving upon the decade-old ratio of $3+ε$. Our approach is based on two components, each of which, we believe, is of independent interest. First, we show that in order to give an $α$-approximation algorithm for $k$-median, it is sufficient to give a \emph{pseudo-approximation algorithm} that finds an $α$-approximate solution by opening $k+O(1)$ facilities. This is a rather surprising result as there exist instances for which opening $k+1$ facilities may lead to a significant smaller cost than if only $k$ facilities were opened. Second, we give such a pseudo-approximation algorithm with $α= 1+\sqrt{3}+ε$. Prior to our work, it was not even known whether opening $k + o(k)$ facilities would help improve the approximation ratio.
1 Introduction
The paper addresses k-median's hard facility-count constraint through pseudo-approximation, showing that opening a constant number of extra facilities can be reconciled with a k-facility solution. It combines this reduction with a pseudo-approximation algorithm to improve over the previous 3+ϵ guarantee.
- Problem setting: k-median chooses k facilities minimizing clients' total distance to their nearest opened facility.The problem is NP-hard and applies to polling-station placement, clustering, data mining, and supply allocation.
- Prior work: 3+ϵ was the previous best approximation guarantee for solutions opening exactly k facilities.Arya et al.'s local-search algorithm achieves this ratio with running time n^2/ϵ.
- Our approach: A pseudo-approximation algorithm opening k+c facilities with cost at most α times optimum can be transformed into an α+ϵ approximation opening only k facilities.The transformation runs in time n^O(c/ϵ) times the pseudo-approximation algorithm's running time.
- Our approach: The algorithm's two components are a reduction from constant-additive pseudo-solutions and a pseudo-approximation based on bi-point solutions.The bi-point solution is converted into an integral solution with k+O(1/ϵ) opened facilities.
- Our results: The approach improves the previous 3+ϵ approximation while opening only k+O(1/ϵ) facilities in its pseudo-approximation stage.The paper identifies this as an improvement over prior pseudo-approximation algorithms requiring k+Ω(k) facilities.
- Implications: Allowing k+1 facilities eliminates the showcased natural-LP integrality-gap instance, where k facilities cost 2 but opening all leaves costs 0.The example is a star with k+1 leaf facilities and clients.
2 Obtain solutions from additive pseudo-solutions
The section reduces pseudo-solutions to valid k-facility solutions by restricting attention to sparse instances and carefully removing or replacing facilities.
- Sparse instances: A facility is A-sparse when no facility violates the paper’s density condition, while a facility violating it is A-dense.The nearest optimal facility distance d(i, OPTI) is used in this condition.
- Sparse instances: Sparse instances prevent large cost reductions from opening O(1) additional facilities, addressing the central obstacle to converting pseudo-solutions.The motivating gap instance is not A-sparse because two omitted leaf facilities are A-dense for A < optI/2.
- Obtaining sparse instances: Algorithm 1 enumerates n^O(t) residual instances by guessing dense facilities and their nearest optimal facilities, then removing selected facilities.At least one enumerated instance is optI/t-sparse while preserving an optimal solution.
- Obtaining sparse instances: The residual instance I′ preserves OPTI as an optimal solution because Algorithm 1 removes no facility opened by OPTI.Thus, solutions to I′ transfer to the original instance with the same cost.
- Converting pseudo-solutions: Algorithm 2 starts with a c-additive pseudo-solution, repeatedly removes cheap facilities while more than k remain, and otherwise searches candidate sets D and V.The search requires |D| + |V| = k and |V| < t, and returns a solution with at most k facilities.
- Converting pseudo-solutions: The conversion increases cost by at most cB when the removal loop terminates early; otherwise, determined facilities and nearby replacements support the bounded-cost candidate construction.Determined means ℓ_i < δL_i, where L_i is the nearest-neighbor distance in T′ and ℓ_i is distance to OPTI.
3 An O(1/ϵ)-additive 1 +3 + ϵ approximation for k-median
The section converts a bi-point solution into an integral solution opening only O(1/ϵ) additional facilities, while controlling connection cost to obtain the stated approximation guarantee.
- Bi-point solutions: A bi-point solution aS1 + bS2 satisfies a + b = 1, |F1| ≤ k < |F2|, and a|F1| + b|F2| = k.Its fractional connection cost is ad1 + bd2, where d1 and d2 are the total connection costs to F1 and F2.
- Star-based rounding: The rounding framework represents F2 facilities as stars centered at their closest facilities in F1, enabling controlled exchanges between centers and leaves.For clients incident to a star, the center provides distance at most d1(j) + 2d2(j).
- Star-based rounding: The algorithm opens all facilities of selected small stars, samples leaves of large stars, and uses randomized grouping to preserve approximate opening probabilities a and b.Small stars are partitioned into ⌈2/(abη)⌉ groups, while large stars are handled individually.
- Earlier cases: An earlier knapsack-based rounding case achieves expected cost at most (1 + a)d2 + ad1 while opening at most k + 2 facilities.The method rounds an optimal knapsack-LP solution with at most one fractional variable.
- Facility bound: The randomized rounding opens at most k + 3⌈2/(abη)⌉ facilities.Large stars contribute within their fractional budget, while each group of small stars incurs at most an additive constant; the number of groups bounds the total excess.
- Cost analysis: The resulting solution has expected connection cost at most (1 + η)(ad1 + b(1 + 2a)d2).The bound follows from the probabilities of opening facilities in F1 and F2 and the fallback distance through a star center.
- Approximation guarantee: The analysis establishes min{d1, ad1 + b(1 + 2a)d2} ≤ (1 + √3/2)(ad1 + bd2), yielding the section’s approximation bound.Combining the bi-point solution’s factor-two cost and the conversion factor gives the stated 3+ϵ over 2 approximation to the bi-point solution.
4 Discussion
The paper's discussion highlights a stronger-than-expected role for pseudo-approximation in k-median and identifies several directions for understanding relaxed facility-count constraints.
- Discussion: Theorem 4 converts any pseudo-approximation opening k + O(1) facilities into a k-facility approximation with essentially the same guarantee.This establishes that constant additive violations of the facility limit need not reduce the approximation guarantee.
- Discussion: 3 + ε is the paper's improved approximation guarantee over the previous best 3 + ε guarantee.
- Discussion: The pseudo-approximation viewpoint may help overcome the natural LP's lower bound of 2 on the integrality gap for k-median.The discussion links this possibility to the goal of matching the 1 + 2/e hardness threshold.
- Discussion: The authors pose the open question of the maximum ratio between the optimum using k + O(1) facilities and the natural LP value using k facilities.
- Discussion: Theorem 4 also motivates studying other hard constraints as soft constraints whose violations may increase runtime.The paper gives slightly violated capacities in capacitated facility location and k-median as related examples.