§3, p. 6 — a schedule of makespan at most makes the residual LP feasible
ProvedUnrelatedSched.FixedMachines.residual_lp_feasiblelinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be an matrix of positive integer processing times, an integer deadline and . Let be a schedule with makespan at most . Let be its partial schedule of long assignments: assigns job to when and leaves unassigned otherwise, and let be the total processing time of the long assignments to machine . Then
- is an admissible schedule of long assignments ( for every ), and
- the – matrix with exactly when job is unassigned by and is a feasible solution of the residual linear program: (LP) of the Rounding Theorem for the unassigned jobs, with deadlines and threshold .
In the paper: "If the instance has a feasible schedule, then this includes a partial schedule of long assignments … If we then set , we see that the linear program (LP) must once again have a feasible solution." This is what makes a 'no' answer of the procedure correct.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_FixedMachines_LongAssignment
Formal statement
namespace UnrelatedSched.FixedMachines
open MatousekLP.Scheduling
/-- §3, p. 6: if `σ` is a schedule with makespan at most `d`, then its long assignments
(`L j = some (σ j)` exactly when `p_{σ(j) j} > ε d`) form an admissible schedule of long
assignments, and the 0-1 matrix of `σ` on the remaining jobs is a feasible solution of the
residual LP with `d_i = d - t_i` and `t = ε d`. -/
theorem residual_lp_feasible {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ)
(hP : ∀ i j, 0 < P i j) (ε : ℝ) (hε : 0 < ε) (d : ℕ) (σ : Fin n → Fin m)
(hσ : makespan (fun i j => (P i j : ℝ)) σ ≤ (d : ℝ)) :
let L : Fin n → Option (Fin m) :=
fun j => if ε * (d : ℝ) < (P (σ j) j : ℝ) then some (σ j) else none
IsAdmissible P ε d L ∧
(fun i j => if L j = none ∧ σ j = i then (1 : ℝ) else 0) ∈ ResidualLP P ε d L := by sorry
end UnrelatedSched.FixedMachines
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 6, Section 3, proof of Theorem 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.