Lemma 8.3.3 — rounding a basic optimal solution of LPR(T) gives makespan at most t* + T
ProvedMatousekLP.Scheduling.rounding_makespan_leLet be running times of jobs on machines and let . Suppose is an optimal solution of the linear program (so is feasible and is its optimal value) that satisfies Assumption 8.3.1. Then there is a schedule , assigning every job to a machine with
whose makespan satisfies
The schedule rounds the fractional assignment along the edges of its support graph; this is the rounding step of the Lenstra–Shmoys–Tardos 2-approximation for scheduling on unrelated machines.
Formalization Note The book says "we can efficiently construct a schedule"; the running time of the construction is not formalized. What is formalized is the property of the schedule that the proof constructs: each job goes to a machine with , i.e. along an edge of the support graph. Without this constraint the statement would still be meaningful but would not describe the rounding. Machines are Fin m, jobs Fin n.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_MatousekLP_Scheduling_LPRelaxation
namespace MatousekLP.Scheduling
/-- Lemma 8.3.3 (Matoušek–Gärtner, p. 152), in the form produced by its proof. Let
`T ≥ 0` and let `(t*, x*)` be an optimal solution of `LPR(T)` (so `LPR(T)` is feasible
and `t*` is its optimal value) satisfying Assumption 8.3.1. Then there is a schedule
`σ` that assigns every job `j` to a machine `σ(j)` with `x*_{σ(j) j} > 0` (along an
edge of the support graph `G`), and whose makespan is at most `t* + T`. -/
theorem rounding_makespan_le {m n : ℕ} (d : Matrix (Fin m) (Fin n) ℝ)
(hd : ∀ i j, 0 < d i j) (T : ℝ) (hT : 0 ≤ T) (tstar : ℝ)
(xstar : Matrix (Fin m) (Fin n) ℝ)
(hopt : LPROptimal d T tstar xstar) (hA : Assumption831 d T xstar) :
∃ σ : Fin n → Fin m, (∀ j, 0 < xstar (σ j) j) ∧ makespan d σ ≤ tstar + T := by sorry
end MatousekLP.Scheduling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.