§3.3 — LP rounding gives a vertex cover of at most twice the minimum size
ProvedMatousekLP.Integrality.vertex_cover_lp_roundingapproximation-algorithmslinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1vertex-cover
Let be a finite graph (not necessarily bipartite), and let be an optimal solution of the LP relaxation (3.3),
Define and let be a vertex cover of of the minimum possible size. Then is a vertex cover of , and
This is the analysis of the LP-rounding 2-approximation algorithm for minimum vertex cover.
Formalization Note Vertex covers are Mathlib's SimpleGraph.IsVertexCover; minimality of is the hypothesis that no vertex cover has fewer elements.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Integrality_VertexCoverLP
Formal statement
namespace MatousekLP.Integrality
theorem vertex_cover_lp_rounding {V : Type*} [Fintype V] (G : SimpleGraph V)
(xstar : V → ℝ) (hx : IsVCRelaxOptimal G xstar)
(SOPT : Finset V) (hcov : G.IsVertexCover (SOPT : Set V))
(hmin : ∀ C : Finset V, G.IsVertexCover (C : Set V) → SOPT.card ≤ C.card) :
G.IsVertexCover {v | 1 / 2 ≤ xstar v} ∧
(Finset.univ.filter (fun v => 1 / 2 ≤ xstar v)).card ≤ 2 * SOPT.card := by sorry
end MatousekLP.Integrality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, §3.3, p. 38, claim |S_LP| ≤ 2·|S_OPT| (LP relaxation (3.3): p. 37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.