Lemma 5 — projection distance for independent small hyperplanes
ProvedKarpPapadimitriou.Generator.lemma_5ellipsoid-methodp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-geometry
Let be affinely independent small hyperplanes, let lie on , and put . For the paper's parameter ,
This bounds the movement caused by adding one independent equality to the current flat.
Formalization Note All distances use the Euclidean metric on real space. The report's proof shifts between indices and ; the theorem follows its stated indices.
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_Generator_Hyperplanes
Formal statement
namespace KarpPapadimitriou.Generator
/-- Lemma 5: projecting onto one additional independent small hyperplane increases the
distance by at most the displayed factor. -/
theorem lemma_5 (n P j : ℕ) (c : Fin n → ℤ) (k : ℤ)
(H : Fin (j + 2) → (Fin n → ℤ) × ℤ)
(r : EuclideanSpace ℝ (Fin n))
(hsmall : ∀ i, SmallHyperplane P (H i).1 (H i).2)
(hind : IndependentNormals H)
(hr : ∀ i : Fin (j + 2), i.val ≤ j → r ∈ hyperplane (H i).1 (H i).2) :
Metric.infDist r (flat H) ≤
((2 : ℝ) ^ tParam n P c k - 1) *
hyperplaneDistance (H ⟨j + 1, by omega⟩).1 (H ⟨j + 1, by omega⟩).2 r := by sorry
end KarpPapadimitriou.Generator
Source
Karp & Papadimitriou, On linear characterizations of combinatorial optimization problems, MIT/LCS/TM-154 (Feb. 1980), p. 13, Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.