Theorem 8.3.4 — LP rounding schedules unrelated machines within twice the optimal makespan
ProvedMatousekLP.Scheduling.lst_two_approximationLet jobs be scheduled on machines, job taking time on machine , and let be the makespan of an optimal schedule . For let be the optimal value of the linear program , with when it is infeasible. Let minimize over all real , and let be an optimal solution of satisfying Assumption 8.3.1 (for instance a basic optimal solution).
Then the rounding of Lemma 8.3.3 applied to yields a schedule that assigns each job to a machine with and whose makespan is at most twice the optimum:
This is the 2-approximation algorithm of Lenstra, Shmoys and Tardos (1990) for minimizing the makespan on unrelated parallel machines, an NP-hard problem.
Formalization Note "The algorithm in the proof of Lemma 8.3.3 computes a schedule" is formalized by the property of that schedule: it uses only edges of the support graph of (). Without this constraint the conclusion would be trivial, since itself has makespan . Minimality of is the hypothesis for every real and every optimal solution of . The running time of the algorithm is not formalized. Machines are Fin m, jobs Fin n.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_MatousekLP_Scheduling_LPRelaxation
namespace MatousekLP.Scheduling
/-- Theorem 8.3.4 (Matoušek–Gärtner, p. 155; Lenstra–Shmoys–Tardos). Let `T*` minimize
`t*(T) + T` over all real `T` (with `t*(T) = ∞` when `LPR(T)` is infeasible), and let
`(t*, x*)` be an optimal solution of `LPR(T*)` satisfying Assumption 8.3.1. Then the
rounding of Lemma 8.3.3 yields a schedule `σ` that assigns every job `j` along an edge of
the support graph (`x*_{σ(j) j} > 0`) and has makespan at most `2 t_opt`, where `t_opt`
is the makespan of an optimal schedule `σopt`. -/
theorem lst_two_approximation {m n : ℕ} (d : Matrix (Fin m) (Fin n) ℝ)
(hd : ∀ i j, 0 < d i j) (σopt : Fin n → Fin m) (hσopt : IsOptimalSchedule d σopt)
(Tstar tstar : ℝ) (xstar : Matrix (Fin m) (Fin n) ℝ)
(hopt : LPROptimal d Tstar tstar xstar) (hA : Assumption831 d Tstar xstar)
(hmin : ∀ (T t : ℝ) (x : Matrix (Fin m) (Fin n) ℝ),
LPROptimal d T t x → tstar + Tstar ≤ t + T) :
∃ σ : Fin n → Fin m, (∀ j, 0 < xstar (σ j) j) ∧
makespan d σ ≤ 2 * makespan d σopt := by sorry
end MatousekLP.Scheduling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.