Eq. (6.8), p. 346 — 1 − (2/π) arcsin(t) ≥ 0.878(1 − t) for all t ∈ [−1, 1]
ProvedConvexOptAlg.GoemansWilliamson.eq_6_8arcsingoemans-williamson-constantinequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1real-analysis
For every real ,
This one-variable inequality is the source of the Goemans–Williamson constant: the best constant is , and lies below it. The book uses (6.8) without proof in the proof of Theorem 6.11.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_GoemansWilliamson_Defs
Formal statement
namespace ConvexOptAlg.GoemansWilliamson
/-- Inequality (6.8) (Bubeck, arXiv:1405.4980v2, proof of Theorem 6.11, p. 346):
`1 − (2/π) arcsin(t) ≥ 0.878 (1 − t)` for all `t ∈ [−1, 1]`. -/
theorem eq_6_8 (t : ℝ) (ht : t ∈ Set.Icc (-1 : ℝ) 1) :
1 - 2 / Real.pi * Real.arcsin t ≥ (0.878 : ℝ) * (1 - t) := by sorry
end ConvexOptAlg.GoemansWilliamson
Source
Bubeck, arXiv:1405.4980v2, Eq. (6.8), proof of Theorem 6.11, p. 346
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.