§3, pp. 5–6 — the LP rounding procedure is a 2-relaxed decision procedure
ProvedUnrelatedSched.TwoApprox.lp_procedure_two_relaxedapproximation-algorithmslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let , let be a vertex selector for (for each it returns a vertex of (LP) with , or 'none' exactly when that LP is infeasible), and let be the LP rounding procedure driven by : it answers 'no' at exactly when returns 'none', and otherwise it answers with a schedule supported on the chosen vertex that solves (IP) with . Then is a -relaxed decision procedure: for every ,
- if answers with a schedule , then ;
- if answers 'no', then every schedule has makespan greater than .
Together with Lemma 1 this gives the paper's 2-approximation algorithm.
Formalization Note The LP solver's choice of vertex is quantified over through the selector ; finding a vertex in polynomial time (the ellipsoid method) is not formalized.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP import Definitions.Def_UnrelatedSched_TwoApprox_Algorithm
Formal statement
namespace UnrelatedSched.TwoApprox
/-- §3, pp. 5–6: the LP rounding procedure is a 2-relaxed decision procedure. -/
theorem lp_procedure_two_relaxed {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ)
(V : ℕ → Option (Matrix (Fin m) (Fin n) ℝ)) (hV : IsVertexSelector P V)
(D : DecisionProcedure m n) (hD : IsLPRoundingProcedure P V D) :
IsRelaxedDecisionProcedure P 2 D := by sorry
end UnrelatedSched.TwoApprox
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), pp. 5–6, §3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.