p. 7, proof of Theorem 1, (i)⇔(ii) — ⟨z,c,k⟩ ∉ D(C) iff c·x < k on all of CH(S(z))
ProvedKarpPapadimitriou.Facial.notMem_DLang_iff_lt_on_hullconvex-hulllinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a combinatorial optimization problem, , and . Then the following are equivalent:
- ;
- the program subject to has optimal value , read as
This is the first step of the proof of Theorem 1: it replaces the combinatorial question by a statement about the convex hull, to which linear programming applies.
Formalization Note "Has optimal value " is read as "every feasible point has value "; this reading is meaningful also when is empty (vacuously true) and when the objective is unbounded (false), and under it the equivalence holds for every . The triple is its code over .
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_Facial_FacialDescription
Formal statement
namespace KarpPapadimitriou.Facial
theorem notMem_DLang_iff_lt_on_hull (C : COP) (z : List Bool) (hz : z ∈ C.L)
(c : Fin (C.n z) → ℤ) (k : ℤ) :
encTriple z c k ∉ DLang C ↔
∀ x ∈ hull C z, (fun j => (c j : ℚ)) ⬝ᵥ x < (k : ℚ) := by sorry
end KarpPapadimitriou.Facial
Source
Karp & Papadimitriou, On linear characterizations of combinatorial optimization problems, MIT/LCS/TM-154 (Feb. 1980), pp. 7–8, proof of Theorem 1, (i)⇔(ii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.