Theorem 2 — binary search over rounded vertices of (LP) is a 2-approximation algorithm for R||C_max
ProvedUnrelatedSched.TwoApprox.theorem_2Consider the minimum makespan problem on unrelated parallel machines: machines, jobs, and processing times that are positive integers; let be the minimum makespan. Fix any vertex selector (an LP solver returning, for each deadline , a vertex of (LP) with when that LP is feasible, and 'none' otherwise). Then
- an LP rounding procedure driven by exists: a decision procedure that answers 'no' exactly when does, and otherwise answers with a schedule supported on the chosen vertex that solves (IP) with ; and
- for every such , the schedule output by the binary search of Lemma 1 driven by satisfies
This is the paper's main result: a polynomial algorithm for with a constant performance guarantee, where the best bound known before was times the optimum (Davis and Jaffe).
Formalization Note The paper states: "There is a 2-approximation algorithm for the minimum makespan problem on unrelated parallel machines that runs in time bounded by a polynomial in the input size." Its proof establishes that binary search (Lemma 1) over the procedure that rounds a vertex of (LP) with (Theorem 1) outputs a schedule of makespan at most ; this guarantee, for the algorithm as defined and for every choice of vertex by the LP solver, is what is formalized. Polynomial running time (Lemma 1's iteration count, the ellipsoid method, the rounding) is not. The output is tied to the algorithm: it is the binary search's output, and every 'almost' answer is a rounding of the LP solver's vertex, so no optimal schedule can be substituted for it.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP import Definitions.Def_UnrelatedSched_TwoApprox_Algorithm
namespace UnrelatedSched.TwoApprox
open MatousekLP.Scheduling
/-- Theorem 2, p. 6: for every vertex selector, the LP rounding procedure exists, and the binary
search of Lemma 1 driven by any such procedure outputs a schedule of makespan at most twice the
optimum. -/
theorem theorem_2 {m n : ℕ} (hm : 0 < m) (P : Matrix (Fin m) (Fin n) ℕ) (hP : ∀ i j, 0 < P i j)
(V : ℕ → Option (Matrix (Fin m) (Fin n) ℝ)) (hV : IsVertexSelector P V)
(σopt : Fin n → Fin m) (hopt : IsOptimalSchedule (realTimes P) σopt) :
(∃ D : DecisionProcedure m n, IsLPRoundingProcedure P V D) ∧
∀ D : DecisionProcedure m n, IsLPRoundingProcedure P V D →
makespan (realTimes P) (binarySearch P hm D) ≤ 2 * makespan (realTimes P) σopt := by sorry
end UnrelatedSched.TwoApprox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.