Theorem 1 (Rounding Theorem) — every vertex of (LP) rounds to a 0-1 solution of (IP) on its support
ProvedUnrelatedSched.TwoApprox.theorem_1Let , deadlines and a threshold . Suppose the linear program
is feasible, and let be any vertex of this polytope. Then can be rounded to a feasible solution of the integer program
with only where . In schedule form: there is a schedule with for every job, , and load at most on every machine .
The Rounding Theorem is the key tool of the paper: it converts a fractional solution of the deadline LP into a schedule that overshoots each deadline by at most , the largest processing time allowed.
Formalization Note The paper states "and this rounding can be done in polynomial time"; running time is not formalized. "Rounding" is formalized as support containment (), which in particular keeps every integral entry . The paper takes and ; the proof never uses integrality, so real and real are allowed. Feasibility of (LP) is implied by the existence of a vertex.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP
namespace UnrelatedSched.TwoApprox
/-- Theorem 1 (Rounding Theorem), p. 3: every vertex `x̃` of (LP) can be rounded to a 0-1 solution of
(IP) supported on `x̃`. -/
theorem theorem_1 {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ) (d : Fin m → ℝ) (t : ℝ) (ht : 0 ≤ t)
(x : Matrix (Fin m) (Fin n) ℝ) (hx : IsLPVertex P d t x) :
∃ σ : Fin n → Fin m, SupportedOn x σ ∧ IPFeasible P d t σ := by sorry
end UnrelatedSched.TwoApprox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.