A Better-than-2 Approximation for k-Median Part I: The Power of General Bids

1 Introduction

• Metric k-median has a hardness threshold of 1 + 2/e, while prior work reached (2 + ε); this paper asks whether factor 2 is a barrier.The LMP framework combines a facility-location approximation with bi-point rounding, which adds a factor of 2; earlier LMP improvements and rounding refinements reached 2.613.Source: §1 · p. 3

1.1 Our Contribution

• Theorem 1.1 gives a randomized polynomial-time 1.95-approximation for k-median, while Theorem 1.2 gives a polynomial-time solution with at most k + O(log n/ε²) centers and cost at most (1.9499 + ε) · opt.Source: §1.1 · pp. 3–4
• A polynomial-time 1.9499-LMP algorithm for uncapacitated facility location uses generalized bids, including β(α, d) = [α − 1.224d]+, instead of Greedy’s linear bid.The analysis studies how bid choice changes the factor-revealing program; general bids lead to nonlinear programs, and piecewise-linear bids to a family of LPs.Source: §1.1 · pp. 4–5
• A black-box transfer makes generalized bids log-adaptive: a factor-revealing-program bound of ρ carries over with additive ε loss and at most k + O(log n/ε²) centers.The transfer adapts the log-adaptive framework of without repeating the smooth algorithm’s approximation analysis from scratch.Source: §1.1 · p. 5

1.2 Further Related Work

• The related-work discussion situates the result among factor-revealing LP and dual-fitting methods, local search, bi-point rounding, and smooth algorithms for Euclidean k-median.It notes that no LMP-based bi-point rounding approach can breach the (1 + 2/e)√ϕ ≈ 2.208 barrier.Source: §1.2 · pp. 5–6

1.3 Outline

• The paper outlines general bidding functions, their factor-revealing analysis, the log-adaptive transfer, and the full dual-fitting proof of the 1.9499 bound.The outline assigns these topics to Sections 3–6.Source: §1.3 · p. 6

AI Acknowledgment and Concurrent Work

• The authors report that the mathematical proofs were developed without AI, while AI tools assisted proof-checking, writing, and feedback; concurrent work also reported better-than-2 approaches.The concurrent approaches described include an optimal (1 + 2/e + ε)-approximation and independent 2 − σ guarantees.Source: AI Acknowledgment and Concurrent Work · p. 6

2 Preliminaries

• Metric facility location minimizes client connection costs plus a uniform opening cost for each open facility.The optimum value is denoted OPT_f, or OPT when the opening cost is clear.Source: §2 · pp. 6–7
• Metric k-median seeks at most k facilities minimizing the total connection cost from clients to their nearest open facility.The distance from a client to a facility set is the minimum metric distance to any facility in that set.Source: §2 · pp. 6–7
• The Lagrangian viewpoint replaces the cardinality constraint with an opening-cost penalty, while an LMP guarantee bounds cost after facility-opening costs are included.A facility-location algorithm produces solutions at different opening costs; the framework seeks to recover a near-optimal k-median solution from them.Source: §2 · p. 7
• The analysis assumes distances are polynomially bounded and bounded away from zero, following a standard reduction.The passage does not specify the concrete bounds.Source: §2 · p. 7

3 Greedy Algorithm with General Bids

• Generalized Greedy raises client values uniformly; facilities open when their total bids cover opening costs, while active clients become served upon reaching an open facility.Active and inactive clients bid using the same function, with inactive clients’ current service distance as their value.Source: §3 · pp. 7–8

3.1 Motivation for General Bidding Functions

• In the classical tight example, one separated client can open f′ before n−1 co-located clients fund f, forcing those clients to raise their values before connecting.The example uses two facilities at distance 2, with n−1 clients at f and one client at distance 1 from both facilities.Source: §3.1 · p. 8, Figure 1 · p. 8
• For γ∈(1,1.224], the Figure 2 example’s tight ratio is 2−(1−γ)^2, yielding a 1.9499-LMP guarantee at γ=1.224.The generalized example makes the two facilities tight at the same time.Source: §3.1 · p. 9, Figure 2 · p. 9
• The analysis uses each client’s actual attributed cost, not merely the upper bound cost_j≤α_j, because an example using the bound approaches a ratio of 2.The passage identifies the adjusted Figure 1 example as showing this limitation.Source: §3.1 · p. 10

3.2 Properties of Bidding Functions

• Admissible bids are nonnegative, budget-limited, continuous, monotone, scale-equivariant, and superadditive.Scale equivariance preserves the bidding rule under uniform rescaling; superadditivity bounds a two-step reconnection bid by the direct bid.Source: §3.2 · p. 11
• A client’s total cost includes its initial inactivity bid, later connection-improvement bids, and final connection distance; general bids lose the classical telescoping identity.Even for βγ(α,d)=[α−γd]+, the analysis may require a family of 2^Θ(n^2) linear programs rather than the classical single linear program.Source: §3.2 · pp. 11–12

4 Approximation Guarantees

• The factor-revealing program models clients assigned to one optimal facility, ordering them by their final α-values and tracking their connection distances as the algorithm runs.Its constraints encode monotonicity, triangle inequalities, metric inequalities, and the restriction that bids toward a facility do not exceed its opening cost.Source: §4 · pp. 12–13
• An upper bound on the factor-revealing program’s optimum gives an LMP guarantee: running Algorithm 1 with facility cost ˆf = ρf yields a ρ-LMP approximation.The reduction applies when ρ upper-bounds the program’s optimum over all n ≥ 1.Source: §4 · p. 13
• 1.9499-LMP is achieved by Algorithm 1 using bids β(α, d) = [α − 1.224d]+ and facility cost ˆf = 1.9499f.The factor-revealing program is bounded by 2 − (γ − 1)^2 for γ ∈ [1, 1.224], yielding the stated guarantee at γ = 1.224.Source: §4 · pp. 13, 15
• General bids make the factor-revealing objective nonlinear, so the analysis replaces one LP with a family of LPs indexed by binary bid-positivity variables.The constraints are linearized with epigraph variables, while binary variables indicate whether each bid is positive; dualizing the inner LPs gives a family of dual programs.Source: §4 · p. 14
• An adaptive dual solution uses each client’s first nonzero bidding time and a threshold-defined index group to construct feasible solutions for the inner programs.For γ ∈ (1, 1.224], the construction gives value at most 2 − (γ − 1)^2, with correct advice variables established through a continuity argument.Source: §4 · pp. 14–15

5 Log-Adaptive Algorithm

• Following, the algorithm uses log-adaptive steps and a merging procedure to obtain a k-median solution opening k + O(log n) centers.The authors state that their analysis strategy for the log-adaptive algorithm is substantially different from.Source: §5 · p. 15
• Rather than redoing the classical Greedy analysis, the proof shows the algorithm induces a feasible factor-revealing-program solution and transfers its upper bound to algorithm cost.The passage contrasts this approach with the analysis of, which redoes the analysis of [JMM+03] in the log-adaptive context.Source: §5 · p. 15
• Algorithm 2 is an LMP-approximation algorithm with factor (1 + 2δ)ρ, where ρ upper-bounds the factor-revealing program; its connection cost is bounded by (OPT − |S⋆| · f) times that factor.Source: §5 · p. 17

5.2 Algorithm Properties

• The algorithm maintains a no-overbidding invariant, and same-step Stage 2 candidate facilities are either within δθ of each other or at least θ/γ apart.The latter clusterability property is used to prove feasibility for the factor-revealing program.Source: §5.2 · pp. 18, 20
• In Stage 2, a qualifying client becoming inactive while an optimal facility is a candidate forces the opened facility within δθ and makes the other active clients in the specified set inactive in the same step.The lemma assumes ρ ≥ 1.01γ, α*_j ≥ ρ·d(j,i*) for clients in D*, and α*_j > θ for the client that becomes inactive.Source: §5.2 · p. 21

5.3 Algorithm Cost

• The algorithm’s opening-cost analysis bounds client contributions using β on successive r-variable values, then combines those bounds with connection costs to bound total cost.The cost lemma states an upper bound for the solution’s cost with opening cost ˆf, but its bound is not present in the supplied passage.Source: §5.3 · pp. 22–23

5.4 Factor-Revealing Program Feasibility

• For all 1 ≤ j, ℓ < k ≤ n + 1, the constructed variables satisfy r_jk ≤ r_ℓk + d_j + d_ℓ.The section checks feasibility constraints across the algorithm’s three stages; the displayed lemma gives this client-to-client inequality.Source: §5.4 · pp. 23–25

5.5 Proof of Theorem 5.4

• Under its stated conditions, the gluing lemma shows that reindexed variables satisfy the factor-revealing program’s constraints except normalization, which scaling supplies.The proof then uses the program’s upper bound and β’s superadditivity to relate the algorithm’s cost to that bound; the resulting displayed inequality is absent from the supplied passages.Source: §5.5 · p. 26
• The proof bounds CSOL by (1 + 2δ)ρ(OPT − FSOL) and relates ρ·FOPT + ρ·COPT to ρ·OPT.These bounds appear in the proof of Theorem 5.4.Source: §5.5 · p. 27

5.6 k-Median Algorithm Opening k + O(log n) Centers

• Theorem 5.16 gives a polynomial-time k-median algorithm with at most k + O(log n/δ^2) centers and cost at most (1 + δ)ρ·opt.It assumes β(α, d) = [α−γ·d]+, γ ≥ 1, ρ ≥ 1.01γ bounding the factor-revealing program, and sufficiently small δ; the extension uses a robust log-adaptive algorithm and adapts the merging procedure from.Source: §5.6 · p. 27

6.1 Proving a Tight Upper Bound

• For γ in [1, 1.224], the factor-revealing program with βγ(α, d) = [α − γ · d]+ is upper-bounded by 2 − (γ − 1)^2 for all n ≥ 1.The proof handles n = 1 separately; for n ≥ 2 it reduces to bidding matrices with bn,j = 1 for every j, then combines the feasibility and advice-existence lemmas.Source: §6.1 · p. 29

6.2 Constructing a dual certificate from advice

• The procedure uses a bidding matrix and advice to build a profile and assign dual variables, returning a feasible certificate when the advice is correct.It groups clients using their first nonzero bidding times and thresholds derived from the profile; incorrect advice can cause the procedure to return an empty output.Source: §6.2 · pp. 29–31

6.3 Feasibility with correct advice

• With admissible advice for which the procedure succeeds, its output is a feasible dual solution of value 2 − (γ − 1)^2.The proof analyzes a preliminary sent-credit matrix and shifts its diagonal mass to obtain the feasible solution; it also establishes that δ variables satisfying the required property can be assigned.Source: §6.3 · pp. 33–34
• The construction can assign σi,j values satisfying Property 6.18.Source: §6.3 · p. 34
• The assigned variables are nonnegative, and the per-iteration generation bound gi,j ≤ ĝi and total generation constraint are satisfied.Source: §6.3 · pp. 34–35
• Client credit is nonnegative at every iteration, and the client-credit constraints are satisfied for all valid j and i.The proof uses credit expressions that vary across client groups and convex combinations for fractionally assigned clients.Source: §6.3 · p. 36
• The preliminary assignment satisfies nonnegativity, generation, client-credit, and objective constraints; pool-credit nonnegativity and the zero-diagonal convention remain.The pool-credit proof is identified as the lengthiest part of the verification.Source: §6.3 · p. 37
• For i < t1, the pool-credit constraint is satisfied because the resulting lower bound consists of nonnegative stored-credit terms.The broader pool-credit analysis is described as the section’s most involved proof.Source: §6.3 · p. 38
• A feasible factor-revealing dual solution has objective 2-(γ-1)^2 after diagonal repair preserves feasibility and objective value.The preliminary assignment satisfies all constraints except possibly the zero-diagonal condition; the repair enforces it without changing the objective.Source: §6.3 · p. 44

6.4 Existence of correct advice

• The advice-existence proof bounds total produced credit by R0(Γ0) ≤ 1 and R0(Γ1) ≥ 1, then proposes a continuous path to obtain R0(Γ⋆) = 1.The stated strategy uses the intermediate value theorem, contingent on continuity of R0 along the path.Source: §6.4 · p. 45
• The advice path has non-increasing membership values with at most one fractional entry, making every point on it a valid input to the procedure.The at-most-one-fractional-entry property follows because distinct indices differ by at least 1, while fractional values require an index in an open interval of length 1.Source: §6.4 · p. 46
• R0 is continuous along the full path because it is continuous on each section and at every transition between adjacent sections.The path's endpoints are Γ0 at λ = 0 and Γ1 at λ = n.Source: §6.4 · pp. 46–47
• Continuity of R0 along the path from Γ0 to Γ1 implies, by the intermediate value theorem, that some Γ⋆ satisfies R0(Γ⋆) = 1.The proof applies the theorem using Observation 6.47 and Observation 6.48.Source: §6.4 · p. 47
• The Phase 2 budget terms are continuous in λ, and the analyzed sequence is also non-decreasing in λ.For ℓ = n, the memberships stay fixed while the advice value varies; for ℓ < n, the budget expression is non-increasing in the membership values.Source: §6.4 · p. 48
• For t1 < n, R0 is continuous from the left whether the index t−1 exists or is ⊥.When it exists, the update budgets converge to their values at λ; when it is ⊥, continuity follows from the already-continuous R0^(2).Source: §6.4 · p. 50
• When t1 = n and λ > τ̄, t1 remains fixed nearby and continuity of the Phase 1 operations gives continuity of R0(λ).Source: §6.4 · p. 50
• At t1 = n and λ = τ̄, the left limit converges to R0(λ) whether t−1 is absent or exists, completing the continuity proof for all cases.If t−1 is absent, R0(λ−) = λ− → τ̄; otherwise, continuity of the interpolation and updates gives R0(λ−) → R0(λ).Source: §6.4 · p. 51

A The Factor-Revealing Program Bounds the LMP-Approximation Ratio

• A factor-revealing-program upper bound ρ gives Algorithm 1 a ρ-LMP guarantee for UFL when its facility cost is scaled to ρ·f.The proof bounds the algorithm’s cost by ρ times the optimal opening and connection costs.Source: A The Factor-Revealing Program Bounds… · pp. 54, 56
• The analysis represents each client’s distances to facilities opened over time and uses bid superadditivity to bound accumulated payments by bids on selected distances.The proof also accounts for the client’s final connection cost when bounding its contribution.Source: A The Factor-Revealing Program Bounds… · p. 54
• For each optimal facility and its assigned clients, the proof constructs feasible factor-program variables from the algorithm’s distances and payments, then applies the program’s upper bound.It preserves the clients’ original order when re-indexing and normalizes the variables before using ρ.Source: A The Factor-Revealing Program Bounds… · pp. 55–56

B Deriving the Dual

• The dual optimum in Definition 4.5 upper-bounds the original factor-revealing program’s optimum for the linear bidding function.The argument establishes this by relating the intermediate primal to the original program, then using the equivalent dual formulation.Source: B Deriving the Dual · pp. 57, 59, 61
• The reformulated metric constraints use mi for the distance from the central facility to an already-open facility; m1 serves only as slack.The variables need only satisfy the stated structural constraints, including non-increasing values over time.Source: B Deriving the Dual · p. 57
• The family of primal LPs gives an upper bound on the factor-revealing program for bids βγ(α, d) = [α − γ·d]+.The formulation maximizes over a family of primal LPs.Source: B Deriving the Dual · p. 58
• For each fixed choice of binary variables, the intermediate primal and its direct dual have equal optimum values; maximizing over choices preserves the equivalence.The proof uses strong duality after establishing equivalence between the dual representations.Source: B Deriving the Dual · p. 61

Credit calculation for i ≥ fj

• For integral B- and C-clients with i ≥ fj, credit is 1 at i = fj and 1 − ε for i > fj.The B-client calculation gives these values directly, and the C-client calculation is stated to match it.Source: C Dual Fitting Deferred Proofs · p. 63

Dual-fitting deferred proofs

• Fractional assignments are handled as convex combinations of the corresponding group-specific contributions to client credit.The appendix also describes fractional generation and transfer expressions as combinations of the integral cases.Source: C Dual Fitting Deferred Proofs · pp. 62, 63, 66, 69

Credit calculation for i < fj

• Before fj, integral B- and C-clients have credit τ + Rj−1 ≥ 0 for j ≤ i < fj.The calculation is shown explicitly for B-clients and stated to be identical for C-clients.Source: C Dual Fitting Deferred Proofs · p. 66

Budget calculation

• Fractional memberships in groups A–D preserve the stated group bounds because the assigned quantities are convex combinations of their integral-group values.The proof combines the convex-combination definitions with the preceding lemmas, whose arguments do not require integral memberships.Source: C Dual Fitting Deferred Proofs · pp. 70–71
• For clients integral in groups A–D, the budget expression is at most 2 − (γ − 1)^2.The same bound extends to fractional group memberships by linearity and convex combinations.Source: C Dual Fitting Deferred Proofs · p. 71

Proof of Lemma 6.23

• Lemma 6.23 establishes that ˆg_i, g_i,j, t_i,j, and s̄_i,j are nonnegative for every valid i, j.The proof checks phases and groups separately, then uses convex combinations for non-integral clients.Source: C Dual Fitting Deferred Proofs · p. 72

Proofs of Claims 6.40 and 6.41

• Claim 6.40 proves the stated R_j-to-R_i relation by induction on i − j, and Claim 6.41 applies an analogous argument to R′ values.For Claim 6.41, the case t1 = n is trivial; otherwise the proof uses the corresponding relation for ĝ′_i when i > t1.Source: C Dual Fitting Deferred Proofs · pp. 72–73

D k-Median Algorithm Opening k + O(log n) Centers

• The adapted framework yields a k-median algorithm opening at most k + O(log n) centers.The section says this requires a robust version of the Log-Adaptive Algorithm and an adapted merging procedure.Source: D k-Median Algorithm Opening k + O(log… · p. 74
• The algorithm’s η-valid sequence of sequences alternates between type 1 and type 2, with each sequence valid relative to the facilities already opened.A solution has an even number of sequences and ends with all clients inactive.Source: D k-Median Algorithm Opening k + O(log… · p. 75
• The facility-location guarantee for an η-valid solution requires ρ ≥ 1.01γ, sufficiently small δ and ε, and ˆf > nη.The theorem states its guarantee under these parameter conditions; the displayed conclusion is incomplete in the supplied passage.Source: D k-Median Algorithm Opening k + O(log… · p. 75
• Embedding the robust solution into a feasible factor-revealing-program solution is more challenging because a facility may be opened relative to a superset of open facilities.The proof therefore uses a more complicated assignment of the r variables.Source: D k-Median Algorithm Opening k + O(log… · p. 75

D.1 Merging Procedure

• CompleteSolution extends a partial solution, while CompleteSequence extends a partial sequence to a maximal one; their outputs preserve the stated validity conditions.CompleteSolution returns an even-length solution, and CompleteSequence returns a valid sequence containing its input as a prefix.Source: §D.1 · pp. 75–76
• Bisection starts from opening-cost endpoints that yield more than k facilities at the low end and fewer than k at the high end, then narrows the interval until the solutions bracket k.If an endpoint or intermediate solution opens exactly k facilities, it is returned immediately.Source: §D.1 · p. 76
• The merge maintains η-valid solutions on opposite sides of k and either finds an exact-k solution or makes their initial sequences agree, opening at most three new free facilities per step.The two solutions’ parameters differ in at most one entry, by at most η.Source: §D.1 · p. 76
• The bisection-and-merge procedure uses O(log n/ε^2) steps because any η-valid solution has O(log n/ε^2) sequences.The sequence bound follows from geometric growth of θ until all clients become inactive.Source: §D.1 · p. 76
• The final solution costs at most (1 + 9δ)ρ · opt and opens at most k + O(log n) regular facilities.Free facilities are replaced by their regular copies without increasing cost.Source: §D.1 · p. 77

D.2 Merging Procedure Analysis

• For some i ∈ F, there exists i⋆ ∈ F \ S that is (1, 0)-openable with respect to θ and S; a separate result gives (2, 0)-openability with respect to θ and S.Source: §D.2 · p. 77
• The merging analysis preserves sequence validity and maximality when the opening-cost or free-facility parameters differ by at most η.The proof adapts Claim 2 from, while the rest of the analysis is described as identical up to cosmetic changes.Source: §D.2 · pp. 79–80
• Clipping bids to (1 − δ)d(j, S) preserves their triangle inequalities when the active-client set changes between the compared solutions.The proof extends bids to clients newly inactive in one solution and uses the metric triangle inequality to retain the bid constraint.Source: §D.2 · p. 81

E Proof of Theorem D.7

• The proof of Theorem D.7 is completed in Section E.5 and depends on the definitions introduced in Section D through the theorem statement.Source: E Proof of Theorem D.7 · p. 82

E.1 Preliminaries

• An execution processes facility sequences in order, opening their facilities and increasing θ after every even-indexed sequence; each opening or increase is an atomic step.Source: §E.1 · p. 82
• Clients are inactive when θ ≥ (1 − δ)d(j, S), and their α⋆ value is assigned according to how they become inactive.The value is θ for type 1 sequences or free facilities, may be a bid for type 2 sequences, and is (1 − δ)d(j, S) when θ increases.Source: §E.1 · p. 82
• The analysis orders clients by when they become inactive and proves that the associated r values are nonincreasing across successive open-facility sets.Source: §E.1 · pp. 82–83
• A facility that is a candidate with respect to a superset of open facilities is also a candidate with respect to the current open set.Source: §E.1 · p. 84

E.2 Algorithm Properties

• Clients do not overbid toward any facility at any point in the algorithm’s execution.The appendix states this as robust no-overbidding, including for supersets of the open-facility set.Source: §E.2 · p. 84
• Opening facilities and deactivating clients preserve the no-overbidding invariant, while the analysis also checks its preservation when θ increases.The invariant is considered across facility openings, client inactivation, and the increase of θ by a factor of 1+ε2.Source: §E.2 · p. 84
• When two facilities are candidates at the same type-2 step, their distance is at most δθ or at least θ/γ.This separation holds under the stated condition ˆf > nη.Source: §E.2 · p. 86
• If a qualifying client becomes inactive while a regular facility opens, that facility lies within δθ of the candidate i⋆, and all other active clients in D⋆ also become inactive.The lemma assumes ρ ≥ 1.01γ and α⋆j ≥ ρ · d(j, i⋆) for clients in D⋆.Source: §E.2 · p. 88

E.3 Algorithm Cost

• For type-1 openings, active and inactive clients contribute bids based on θ or their distance to the current open set; type-2 openings use τj or the relevant superset’s distance.The type-2 contribution uses distance scaled by 1−δ/2, while type 1 uses 1−δ.Source: §E.3 · pp. 88–89
• Client contributions to facility openings are bounded using β(Zj,k, Rj,k+1) for each relevant opening.The analysis aligns Z with the client’s active or inactive contribution and uses R as a lower bound based on distance to the next opened facility.Source: §E.3 · p. 89
• The total-cost accounting adds |S⋆ reg|nη, and expresses connection cost through Rj,m plus δd(j, S⋆).The extra term compensates for facility payments of ˆf−nη.Source: §E.3 · p. 89

Factor-Revealing Program Feasibility

• When freezing occurs, the opened facility’s geometric properties imply feasibility with respect to S(klast), using the enlarged set S̃(klast) and the resulting client status conditions.Lemma E.11 bounds distances from the opened facility to facilities in S̃(klast); clients in its εθ-neighborhood are inactive or have τj = θ.Source: §E.4 · p. 90
• The algorithm’s cost for clients in D⋆ good is upper bounded, up to a small error, by the factor-revealing program objective using r⋆ variables.The proof compares terms with and without freezing, using superadditivity of β and case analysis when freezing occurs.Source: §E.4 · p. 90
• The constructed ˆf is feasible for the factor-revealing program except for its normalization constraint.The facility constraints are verified by considering when a client becomes inactive: in type 1 and type 2 sequences, or when θ increases.Source: §E.4 · pp. 93–94
• The proof establishes the required pairwise and three-index constraint bounds across cases with and without freezing.For the pairwise bound it uses the triangle inequality and the definition of (2, η)-openability; the three-index proof also considers clients becoming inactive at different times.Source: §E.4 · pp. 94–95

• When j becomes inactive with k, the proof reduces to Lemma E.15; if ℓ ≥ j, j, ℓ, and k deactivate in the same atomic step.Source: §E.4 · p. 95
• For freezing with k ≥ kfirst, the k = n + 1 case is trivial because r*_{j,n+1} = 0; hence the proof assumes k ≤ n.Source: §E.4 · p. 95
• When both j and ℓ are active in S~(k), the claim follows from the triangle-inequality condition for (2, η)-openability; when only j is active, the proof uses active-distance bounds.Source: §E.4 · p. 95
• When j is inactive and ℓ active, inactivity bounds and a distance term d(i*, j) establish the claim; when both are inactive, the d(i*, j) term makes it immediate.Source: §E.4 · p. 95

E.5 Proof of Theorem D.7

• The bound uses ρ as an upper bound on the program’s optimal value, with ρ ≥ 1.01γ.The proof applies this premise to the client groups associated with facilities in the optimal solution.Source: §E.5 · p. 96
• Clients assigned to each optimal facility yield variables satisfying the factor-revealing program’s constraints, after scaling to meet its normalization.The construction relies on Lemmas E.13–E.16 and scale-invariance apart from the normalization constraint.Source: §E.5 · p. 96
• The proof bounds its combined connection- and opening-cost expression by (ρ + 6δ) · OPT.The argument uses an optimal solution with facility cost f = ˆf(ρ + 6δ).Source: §E.5 · pp. 96–97