Lemma 4.1 — edge-wise analysis: the positive- and negative-edge inequalities (24) give expected approximation ratio γ
ProvedHermiteLaptop.MaxAgree.lemma_4_1Consider a special case of the general clustering problem: a weighted edge-labelled instance and a family of feasible clusterings, with . Let , suppose is a relaxation of the problem, and let be an optimal solution of . Suppose a mixture of -spokes roundings applied to always returns a feasible clustering. If for some its collision probability satisfies
then the rounding has expected approximation ratio : , the expectation over the mixture's randomness.
Formalization Note. is a set of labellings; "relaxation" is ∀ C ∈ F, val C ≤ sdpObj a v*; "always feasible" is: for every k with λ_k ≠ 0 and every spoke outcome g, kSpokes v* g ∈ F. The conclusion is γ * val C ≤ Mixture.value I v* for every C ∈ F.
Differences from the source:
- generalization: F a family of clusterings (partitions of V) → F an arbitrary set of labellings Fin n → ℕ; reason: the family of partitions corresponds to the set of labellings inducing them; arbitrary sets include those
- generalization: SDP(a) is a relaxation of the problem → val(C) ≤ SDP(a)-objective of v* for every C ∈ F, i.e. OPT ≤ OPT_SDP; reason: the proof uses only OPT_SDP ≥ OPT; every relaxation in the usual sense satisfies it
- reading: the mixture always returns a feasible solution → for every k with λ_k ≠ 0 and every outcome of the spokes, the k-spokes labelling lies in F; reason: the mixture only runs k-spokes with λ_k > 0
- encoding: expected approximation ratio γ: E[val(C_ALG)] ≥ γ·OPT → γ·val(C) ≤ Σ_k λ_k E[val(k-spokes(v*))] for every C ∈ F; reason: val takes finitely many values, so OPT is attained and the two are equivalent; the mixture expectation by total probability
import Mathlib import Definitions.Def_HermiteLaptop_MaxAgree_Instance import Definitions.Def_HermiteLaptop_MaxAgree_Mixture
namespace HermiteLaptop.MaxAgree
/-- Lemma 4.1 (edge-wise analysis): for a clustering problem with feasible family `F`, `a ∈
[−1/2, 0]`, `SDP(a)` a relaxation, `v` optimal for `SDP(a)`, and a mixture whose k-spokes
outputs on `v` are always feasible, the inequalities (24) `P(ρ) ≥ γ s⁺_a(ρ)` on `[a, 1]` and
`1 − P(a) ≥ γ` give `E[val] ≥ γ · val(C)` for every feasible clustering `C`. -/
theorem lemma_4_1 {n : ℕ} (I : Instance n) (F : Set (Fin n → ℕ)) (a : ℝ)
(ha : a ∈ Set.Icc (-1 / 2 : ℝ) 0) (v : Fin n → EuclideanSpace ℝ (Fin n))
(hv : I.SDPOptimal a v) (hrelax : ∀ C ∈ F, I.val C ≤ I.sdpObj a v) (μ : Mixture)
(hfeas : ∀ k : ℕ, μ.lam k ≠ 0 → ∀ g : Fin k → EuclideanSpace ℝ (Fin n), kSpokes v g ∈ F)
(γ : ℝ) (hγ : 0 ≤ γ)
(hpos : ∀ ρ ∈ Set.Icc a 1, γ * sPlus a ρ ≤ μ.collision ρ)
(hneg : γ ≤ 1 - μ.collision a) :
∀ C ∈ F, γ * I.val C ≤ μ.value I v := by sorry
end HermiteLaptop.MaxAgree
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.