Theorem 4.5 — Algorithm 2 (better of 4-spokes and 5-spokes on an optimal SDP(0) solution) is a 0.7818-approximation for weighted MaxAgree
ProvedHermiteLaptop.MaxAgree.theorem_4_5MaxAgree. Given a weighted edge-labelled simple graph on (, ), find a clustering of maximizing
with no limit on the number of clusters; is the maximum. Algorithm 2 takes an optimal solution of (unit vectors in with pairwise nonnegative inner products maximizing ), forms -spokes and -spokes, and returns the one of larger value.
Theorem 4.5. For every instance and every optimal solution of ,
This improves Swamy's ratio 0.7666 for MaxAgree.
Formalization Note. The conclusion is stated as 0.7818 * val C ≤ algorithm2Value v for every labelling C : Fin n → ℕ, which is equivalent to the bound against . The spokes of and are independent standard Gaussian vectors; ties go to the least index. The expectation is a Bochner integral against the product Gaussian measure.
Differences from the source:
- encoding: E[val(output)] ≥ 0.7818·OPT, OPT the maximum of val over all clusterings → 0.7818·val(C) ≤ E[max(val C4, val C5)] for every labelling C : Fin n → ℕ; reason: val takes finitely many values, so OPT is attained and the two forms are equivalent; no real supremum
- encoding: clusterings of V = {1,…,n} → labellings Fin n → ℕ; reason: every partition is induced by a labelling and val depends only on the partition
- encoding: ties in the argmax "may be broken arbitrarily" → least index among the maximizers; reason: ties have probability zero
- reading: C4 ← 4-spokes(v*), C5 ← 5-spokes(v*) (coupling of the two runs unspecified) → independent spokes: 4 and 5 independent standard Gaussian vectors in ℝⁿ; reason: Algorithm 2 does not say; fresh randomness per call is the natural reading, and the paper's argument (the maximum dominates the mixture) does not depend on the coupling
import Mathlib import Definitions.Def_HermiteLaptop_MaxAgree_Instance import Definitions.Def_HermiteLaptop_MaxAgree_KSpokes
namespace HermiteLaptop.MaxAgree
/-- Theorem 4.5: for MaxAgree, Algorithm 2 (the better of 4-spokes and 5-spokes applied to an
optimal solution of `SDP(0)`) has expected approximation ratio `0.7818`:
`E[max(val C4, val C5)] ≥ 0.7818 · val(C)` for every clustering `C`, hence `≥ 0.7818 · OPT`. -/
theorem theorem_4_5 {n : ℕ} (I : Instance n) (v : Fin n → EuclideanSpace ℝ (Fin n))
(hv : I.SDPOptimal 0 v) (C : Fin n → ℕ) :
(0.7818 : ℝ) * I.val C ≤ I.algorithm2Value v := by sorry
end HermiteLaptop.MaxAgree
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.