Source-linked AI summary
Iterative Randomized Rounding for Better-Than-2 k-Median Approximation
Jarosław Byrka, Yuhao Guo, Yang Hu, Shi Li, Yongho Shin, Phanu Vajanopath, Chengzhang Wan, Zaixuan Wang
TL;DR
The paper asks whether LP-based rounding for metric k-median can improve on factor 2 when a constant number of extra facilities is allowed. It combines complementary rounding methods and a facility-budget reduction, obtaining a 1.9999-approximation with at most k facilities and showing a strictly sub-2 LP integrality gap with constant extra facilities.
Problem
The standard LP relaxation has integrality gap at least 2, and whether that gap falls below 2 with a constant number of extra facilities was an open question of Li and Svensson.
Source: §1.1 · p. 2, §1.2 · p. 3Method
The algorithm preprocesses the LP solution, applies complementary iterative-rounding and filtering-and-bundling roundings, returns the cheaper solution, and uses Li and Svensson’s reduction to meet the k-facility budget.
Source: §1.4 · p. 4Results
1.9999 is the expected-cost approximation factor of the randomized polynomial-time algorithm opening at most k facilities, while the intermediate solution achieves a strictly sub-2 LP ratio with k + O(1) facilities.
Source: §1.2 · p. 3Takeaways & Limitations
The standard LP integrality gap is strictly below 2 when a constant number of extra facilities may be opened, partially answering Li and Svensson’s question.
Source: §1.2 · p. 3The preprocessing assumes clients are connected to their nearest one unit of fractional opening.
Source: §3 · p. 9
Abstract
from arXiv · showhide
We study the classic $k$-median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsilon)$-approximation. Our algorithm opens $k+O(1)$ facilities and achieves an expected connection cost of at most $1.9999$ times the value of the standard LP relaxation. Although the numerical improvement over $2$ is small, it establishes a conceptual result: the integrality gap of the standard relaxation is strictly below $2$ when a constant number of extra facilities is allowed. This partially answers an open question of Li and Svensson [STOC'13]. Combined with their reduction, our result yields a $1.9999$-approximation algorithm for $k$-median. Our approach builds on several technical ingredients. First, we develop a preprocessing routine that makes the LP solution $\mathrm{poly}(\varepsilon)$-integral, at the cost of a $(1+\varepsilon)$ factor in the connection cost and $O(1)$ extra facilities. Unlike the preprocessing of Byrka et al. [FOCS'26], our conversion is unconditional: it requires no special treatment of clients whose fractional facilities are concentrated. Next, we show that the main rounding algorithm can open facilities one at a time, eliminating the batch processing used by Byrka et al. [FOCS'26]. Finally, the improvement over 2 comes from a tighter analysis for clients whose distances from to its facilities are not all equal, and a complementary algorithm for the case in which these distances are nearly uniform.
1 Introduction
The paper studies polynomial-time approximation for metric k-median, where the goal is to connect clients to a limited number of open facilities at minimum total cost. It improves on the factor-2 barrier for LP rounding by combining complementary rounding methods and a reduction to the strict facility budget.
1.1 Previous results
- Earlier work reached a (2 + ε)-approximation through greedy or iterative-rounding approaches, while Li and Svensson’s reduction converts extra-facility solutions to strict-budget solutions.The related-work discussion also surveys facility-location, Euclidean, and fixed-parameter results.Source: §1.1 · pp. 2–3, §1.3 · pp. 3–4
1.2 Our results
- 1.9999 is the expected-cost approximation factor of a randomized polynomial-time algorithm that opens at most k facilities.The intermediate pseudo-approximation opens k + O(1) facilities and achieves expected cost at most 1.9999 times the standard LP value.Source: §1.2 · p. 3
- The factor-2 lower bound for the standard LP is no longer attained when a constant number of extra facilities may be opened.The result partially answers Li and Svensson’s question about the integrality gap under that facility allowance.Source: §1.1 · p. 2, §1.2 · p. 3
1.4 Overview of the techniques
- The algorithm makes the LP solution δ-integral, then applies iterative rounding and filtering-and-bundling rounding and returns the cheaper solution.The conversion uses the reduction of Li and Svensson to obtain a solution opening at most k facilities.Source: §1.4 · pp. 4, 7
- The iterative-rounding analysis is tight only for clients whose fractional support facilities are at nearly equal distances; greater distance spread yields analysis slack.The paper says that the gap in the analysis is proportional to the spread.Source: §1.4 · pp. 4–5
- For concentrated distances, filtering and bundling gives a factor of about 1 + 2/e, while iterative rounding is advantageous when distances are spread out.Both client types can occur in one instance, so the algorithm compares complete rounded solutions rather than choosing a rounding separately for each client.Source: §1.4 · pp. 4, 6
2 Preliminaries
The preliminaries define the LP-based connection-cost framework and the dependent pipage rounding used to manipulate fractional openings. They also state a concentration bound tailored to that rounding.
2 Preliminaries
- For a fixed feasible facility-opening vector, each client is assigned to its nearest one unit of opening, defining its connection cost.The LP describes client assignments and facility openings; the nearest-unit assignment minimizes cost for a fixed opening vector.Source: §2 · p. 7
- Laminar pipage rounding preserves coordinate expectations and rounds each laminar-set total to a neighboring multiple of δ.When a set’s opening total is already a multiple of δ, that total is preserved in every outcome.Source: §2 · pp. 7–8
- Weighted pipage concentration supplies Bernstein-like tail bounds because the independent-variable Bernstein inequality does not directly apply to dependent pipage rounding.The bound applies to a weighted sum of rounded openings and also states that zero variance makes the sum deterministic.Source: §2 · p. 8
3 Preprocessing
The preprocessing converts a feasible LP solution into a finely integral, δ-grid opening vector while keeping expected client connection costs close to their LP costs. It splits nearest-facility mass into heads and tails, atomizes and rounds them, then merges and caps openings while preserving ball deficits; the analysis establishes unconditional cost and facility bounds.
3 Preprocessing
- For 0<ε<1/p, ε≤1/8, and 1/(2ε)∈N, randomized preprocessing outputs δ-integral y′ in n^O(1)ε^-O(p) time with E[cost_y′(j)]≤(1+O(pε))cost_y(j), unconditionally.Here δ=ε^14ℓ+2, and the cost-bound constants are absolute and independent of p.Source: §3 · p. 9, §3.1 · p. 10
3.1 Algorithm
- High-influence atoms are copied, then shared physical and virtual atoms are scaled by 1+θ before pipage rounding; the resulting opening savings offset rounding errors and keep total openings at k+O(1).Virtual atoms can be reassigned to facilities in their associated heads and do not contribute to final openings; this reassignment increases connection cost by at most a 1+O(ε) factor per representative.Source: §3 · p. 9, §3.1 · pp. 11–13
- Each client’s nearest unit is split into a 1−ε head and an ε tail; filtering selects representatives with pairwise-disjoint heads, which can then be rounded independently.Source: §3 · p. 9, §3.1 · pp. 10–11
- Final merging and capping map the opening back to original facilities, keep each coordinate in [0, 1] on the δ-grid, and do not increase total opening or connection costs.Ball deficits remain unchanged because merging preserves opening at every location and capping only changes locations whose opening is already at least 1.Source: §3.1 · p. 16
3.2 Bounding the Number of Open Facilities
- The facility-count analysis treats A0 > 2 and A0 ≤ 2 separately, using bounds on A′ − A and Δ1 to control excess opening.For A0 > 2, the cited bounds hold with probability at least 1 − exp(−Ω(ε^-10ℓ)); for A0 ≤ 2, the bound on Δ1 has that probability.Source: §3.2 · pp. 16–17
3.3 Connection Cost Analysis
- E[costy′(j)] ≤ (1 + O(pε)) costy(j) + 3ε(1 + O(pε)) costy(j) when pε < 1.The analysis bounds small-radius deficit increases additively by O(εθ) and compares larger-radius opening around the representative with radius factor 1 + O(ε) and mass factor 1 + θ.Source: §3.3 · pp. 17, 19
3.3.1 Proof of Lemma 3.11
- For a fractional combination of opening mass m, the expected mass after rounding is at least m − εθ/(1 − ε).This mass bound is one ingredient used to bound the expected deficit increase for small radii.Source: §3.3 · p. 17, §3.3.1 · pp. 20–21
3.3.2 Proof of Lemma 3.12
- For each representative r, the proof constructs a feasible comparison assignment of one unit of rounded opening using heads and retained tail atoms.It retains tail atoms up to min(1/2, y′(Tr)) and allocates retained virtual-atom mass to opened facilities in other heads.Source: §3.3.2 · pp. 21–22
3.4 Putting All Together
- The completed preprocessing has an unconditional cost bound and a facility bound; merging and capping preserve grid integrality, total opening, and all ball deficits.The proof also ensures at least one unit of rounded opening in every outcome when clients exist.Source: §3.1 · p. 16, §3.4 · p. 22
4 A Client-Dependent Bound for the Single-Pivot Rounding Algorithm of [8]
The section refines the single-pivot rounding analysis with a client-dependent bound: the factor is 2 only when a client’s supported facility distances are equal, and otherwise the bound improves with distance dispersion.
4.1 Recap of Rounding Algorithm of [8]
- The single-pivot algorithm chooses a pivot according to current opening and closes other facilities using nearest-unit weights; its expected opening count remains |y|1.It terminates almost surely.Source: §4.1 · pp. 23–24
4.2 Main Theorem and Notations
- 2 − Dj/(12Vj) bounds a client’s approximation factor when Vj > 0, with Dj measuring variation in its supported facility distances.The bound is immediate for a singleton support, where Dj = 0.Source: §4 · p. 23, §4.2 · p. 24
4.3 Saving in One Iteration
- For each iteration before the stopping time, the one-step analysis bounds the expected next charge by the current charge minus a saving Γ.When an outside pivot deletes a facility i in U, its new backup distance is at most min{b, 2di + ri}.Source: §4.3 · pp. 25–26
4.4 Bounding the Saving Term Γ
- The saving term Γ is nonnegative, and the larger of two derived lower bounds is at least D(U)/4.This connects the one-step saving to the dispersion present in U.Source: §4.4 · p. 27
4.5 Dispersion Persistence and Completion of the Proof
- The stopped potential sequence is a supermartingale, and the proof uses optional stopping to relate the terminal client cost to the potential at the stopping time.At termination, the expected client cost is bounded by the potential at t∗.Source: §4.5 · pp. 28–29
5 Converting the LMP Algorithm into One with k + O(1) Open Facilities
This section adapts the LMP rounding algorithm to open at most k + Oε(1) facilities while preserving a client-dependent, dispersion-sensitive cost guarantee up to a 1 + ε loss. It uses a single pivot per iteration and controls opening changes to support concentration bounds, yielding an expected polynomial-time algorithm.
5 Converting the LMP Algorithm into One with k + O(1) Open Facilities
- The conversion selects one pivot per iteration and preserves the refined dispersion-dependent bound by favoring negative-imbalance operations and splitting large deletion sets.Unlike the conversion in, it does not rely on batch pivot selection; the bounded change in total opening enables concentration bounds.Source: §5 · p. 29
5.1 Algorithm
- The algorithm preprocesses openings to be poly(ε)-integral, then samples weighted token operations that open a token’s facility and close a subset of fractional facilities.Operations with negative imbalance receive weight 1 + η, controlling the exponential moment of total opening.Source: §5.1 · pp. 29–30
5.2 Analysis of the Number of Open Facilities
- The facility-count analysis establishes a tail bound for total opening, almost-sure termination with polynomial expected iterations, and rejection probability at most ζ for trials exceeding the budget.Independent trials continue until the number of opened facilities is at most Y0 + s.Source: §5.2 · p. 32
5.3 Analysis of Connection Cost of j
- A local-charge certificate with initial bound Bj yields an expected connection-cost guarantee for each client in the accepted trial.For η = εδ/4 and ζ = ε/4, the stated bound is E[d(j, O)^p] ≤ (1 + ε)Bj, with an additive term specified in the theorem.Source: §5.3 · p. 33
5.4 The dispersion potential and the client-dependent certificate
- For k-median, the dispersion potential has a local-charge certificate with initial bound Bj = 2Vj − Dj/12.This client-dependent certificate supplies the bound used in the connection-cost analysis.Source: §5.4 · p. 36
- Theorem 5.6 and Lemma 5.7 yield a rounding algorithm that returns a facility set satisfying a guarantee for every client.The supplied passages do not include the guarantee’s formula.Source: §5.4 · p. 38
- With Y0 ≤ k + 3 and δ = ε^O(1), the algorithm opens at most k + Oε(1) facilities and runs in expected polynomial time for fixed ε.Here s = O(δ^-2 ε^-2 log(4/ε)); the expectation includes rounding trials and rejection of trials that exceed the facility budget.Source: §5.4 · p. 38
- The conversion preserves the dispersion saving from Section 4 up to a multiplicative 1+ε loss, and both rounding algorithms use the same preprocessed solution in the final combination.Source: §5.4 · p. 38
6 Robust Algorithm
The robust algorithm complements the equal-distance case with a better-than-2 ratio for general distance profiles. It uses assurance radii to filter clients into representative bundles, then applies dependent rounding and analyzes the resulting connection costs.
6 Robust Algorithm
- Theorem 6.1 gives a randomized polynomial-time algorithm returning at most ⌈y(F)⌉ facilities for a complete fractional solution with y(F) ≥ 1.The section presents this algorithm as complementary to the Section 4 algorithm, which achieves ratio 2 only when support distances are equal.Source: §6 · p. 38
6.1 Clients and Their Radii
- For each client, the assurance radius minimizes R + 5e·Tj(R) over radii whose ball contains at least half the support mass; equal support distances yield Aj = Vj.The section also defines Tj(R) as the partial expectation outside the radius-R ball.Source: §6.1 · p. 39
6.2 Algorithm
- The algorithm filters clients into representatives and then applies dependent rounding to a maximum matching of those representatives.Filtering selects the remaining client with minimum assurance radius, then removes clients within 2 max{Rj, Rr}.Source: §6.2 · p. 40, §6.2.1 · p. 41, §6.2.3 · p. 41
6.2.1 Filtering
- Each removed client j has a representative r(j) with Ar(j) ≤ Aj and d(j, r(j)) ≤ 2 max{Rj, Rr(j)}, while distinct representatives are farther apart than twice the larger radius.Source: §6.2.1 · p. 41
6.2.2 Disjoint Bundles
- A representative’s bundle contains its supporting facilities within half its distance to the nearest other representative, and these bundles are pairwise disjoint.Source: §6.2.2 · p. 41
6.2.3 Dependent Rounding
- Dependent rounding ensures each representative’s expected excess connection distance beyond Rr is at most 5Tr.Representatives are greedily paired by closest distance, and rounding is applied to a laminar family containing their bundles and paired unions.Source: §6.2.3 · pp. 41–42
6.3 Analysis
- For a client removed by representative r, the analysis uses d(j,r) + Rr as a service bound when r’s threshold ball is served, and a backup bound otherwise.The section connects this analysis to Theorem 6.1 through Theorems 6.3, 6.5, and 6.11.Source: §6.3 · p. 43
7 Combining the Roundings: An Approximation Below Two
The section combines the rounding components to obtain a pseudo-approximation using k + O(1) facilities, then applies the Li–Svensson reduction. The resulting approximation ratio is at most 1.9999 for sufficiently small ε and ρ.
7 Combining the Roundings: An Approximation Below Two
- The combination targets an α-approximation using k + c facilities for α = 2 − Ω(1) and c = O(1), which the Li–Svensson reduction converts to an (α + τ)-approximation.The reduction runs in time n^O(c/τ) times the pseudo-approximation’s running time.Source: §7 · p. 44
- Preprocessing makes the LP solution δ-integral with δ = ε^O(1), adding three fractional open facilities and increasing cost by a factor of 1 + O(ε).The algorithm compares the cheaper of the two rounding outputs, O1 and O2.Source: §7 · pp. 44–45
- The analysis reports α⋆ ≈ 1.99984277546752 and establishes the facility bound in every outcome.Source: §7 · p. 45
- 1.9999 is the resulting approximation ratio for sufficiently small ε and ρ.The section states that this proves Theorem 1.1.Source: §7 · p. 45