§2.3, (6)–(7) — the warm-start bound
ProvedCFLOutliers.warm_start_boundapproximation-algorithmscapacitated-facility-locationfacility-locationlocal-searchp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be real numbers with , , and , satisfying the two endpoint bounds
Then
In the paper , , and ; the bound turns the signed comparison and the warm start into the factor . The constant is attained at , .
Differences from the source:
- generalization: a = c(S⁻), b = c(S⁺), θ the merge parameter, t = λ⁺g, H = 5 OPT + 6mτ + 3nη → arbitrary reals with 0 < θ ≤ 1, t ≥ 0, H ≥ 0, M ≥ 0 satisfying (6); reason: the derivation on pp.6–7 uses only (6) and these sign conditions, all of which the paper's values satisfy
Preamble
import Mathlib
Formal statement
namespace CFLOutliers
/-- **The warm-start bound** (Dabas, arXiv:2611.04094, §2.3, displays (6)–(7), pp.6–7).
For reals with `0 < θ ≤ 1`, `t ≥ 0`, `H ≥ 0`, `M ≥ 0`, if `a ≤ H − 3θt` and `b ≤ a + t` (6),
then `min{b, a + θ b + M} ≤ (12/11) H + M` (7).
**Formalization Note.** Stated for arbitrary reals meeting (6); in the paper `a = c(S⁻)`,
`b = c(S⁺)`, `t = λ⁺ g`, `H = 5 OPT + 6mτ + 3nη ≥ 0`. -/
theorem warm_start_bound (a b θ t H M : ℝ) (hθ0 : 0 < θ) (hθ1 : θ ≤ 1) (ht : 0 ≤ t)
(hH : 0 ≤ H) (hM : 0 ≤ M) (ha : a ≤ H - 3 * θ * t) (hb : b ≤ a + t) :
min b (a + θ * b + M) ≤ 12 / 11 * H + M := by sorry
end CFLOutliers
Source
R. Dabas, A Constant-Factor Approximation for Capacitated Facility Location with Outliers, arXiv:2611.04094 (preprint; held version, sha256 613f7405…9798), §2.3, pp.6–7, displays (6)–(7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.