Theorem 3 — enumerating long assignments and rounding the LP gives a -approximation for makespan
ProvedUnrelatedSched.FixedMachines.theorem_3Let machines and jobs be given, with a matrix of positive integer processing times, and let be the minimum makespan over all schedules. Let and let be any LP solver returning a vertex of each feasible residual LP (a vertex selector). Then the procedure run with exists, and for every such procedure the binary search of Lemma 1 driven by it returns a schedule with
The paper states: "Let be a fixed integer. There is a family of algorithms such that, for each , is a -approximation algorithm for the minimum makespan problem on unrelated parallel machines that requires time bounded by a polynomial in the input size and space bounded by a polynomial in , , and the input size." Its proof establishes the approximation guarantee above for the algorithm it describes (enumerate long assignments, round a vertex of the residual LP, binary search on the deadline), which is what is formalized.
The result is a polynomial approximation scheme for every fixed number of machines whose space requirement is polynomial in , in contrast with the earlier scheme of Horowitz and Sahni.
Formalization Note The time and space bounds and the hypothesis that is fixed are not formalized; the guarantee is stated for every . The optimum is given by an optimal schedule . The output schedule is tied to the algorithm: it is produced by the binary search from answers of the procedure , each of which extends an admissible schedule of long assignments and rounds a vertex of the residual LP within its support.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_FixedMachines_LongAssignment import Definitions.Def_UnrelatedSched_FixedMachines_BinarySearch
namespace UnrelatedSched.FixedMachines
open MatousekLP.Scheduling
/-- Theorem 3 (p. 6), as its proof establishes it: for every number `m ≥ 1` of machines, every
positive integer processing-time matrix `P`, every `ε > 0` and every LP solver `V`, the
procedure `A_ε` run with `V` exists, and the binary search of Lemma 1 driven by any such
procedure outputs a schedule whose makespan is at most `(1 + ε)` times the optimal makespan. -/
theorem theorem_3 {m n : ℕ} (hm : 0 < m) (P : Matrix (Fin m) (Fin n) ℕ)
(hP : ∀ i j, 0 < P i j) (ε : ℝ) (hε : 0 < ε)
(V : ℕ → (Fin n → Option (Fin m)) → Option (Matrix (Fin m) (Fin n) ℝ))
(hV : IsVertexSelector P ε V) (σopt : Fin n → Fin m)
(hopt : IsOptimalSchedule (fun i j => (P i j : ℝ)) σopt) :
(∃ D : ℕ → Option (Fin n → Fin m), IsAepsProcedure P ε V D) ∧
∀ D : ℕ → Option (Fin n → Fin m), IsAepsProcedure P ε V D →
makespan (fun i j => (P i j : ℝ)) (binarySearch hm P D) ≤
(1 + ε) * makespan (fun i j => (P i j : ℝ)) σopt := by sorry
end UnrelatedSched.FixedMachines
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.