§3, p. 6 — the procedure is a -relaxed decision procedure
ProvedUnrelatedSched.FixedMachines.relaxed_procedureLet be an matrix of positive integer processing times, , and let be any vertex selector (an LP solver that returns a vertex of each feasible residual LP, and returns nothing only for an infeasible one). Then
- the procedure run with exists: there is a decision procedure that tries every admissible schedule of long assignments, rounds the vertex of the residual LP, and combines the result with the long assignments; and
- every such procedure is a -relaxed decision procedure: on every deadline it either answers 'no', in which case no schedule has makespan at most , or returns a schedule of makespan at most .
In the paper: "We try all possible schedules of long assignments in this way, computing the remaining available time on each machine and applying the rounding procedure. Either we conclude that the instance is a 'no' instance, or we produce a schedule with makespan at most ."
Formalization Note The existence clause is where the Rounding Theorem (Theorem 1) enters: each vertex of a feasible residual LP can be rounded, within its support, to an (IP) solution. The paper applies Theorem 1 with , which need not be an integer although Theorem 1 asks for ; the proof of Theorem 1 does not use integrality. Running time is not formalized.
import Mathlib import Definitions.Def_UnrelatedSched_FixedMachines_LongAssignment import Definitions.Def_UnrelatedSched_FixedMachines_BinarySearch
namespace UnrelatedSched.FixedMachines
/-- §3, p. 6: for every LP solver (vertex selector) `V`, the procedure `A_ε` run with `V` exists
(every vertex of a feasible residual LP can be rounded), and every procedure that is `A_ε` run
with `V` is a `(1 + ε)`-relaxed decision procedure: it either answers 'no', in which case no
schedule has makespan at most `d`, or produces a schedule with makespan at most `(1 + ε) d`. -/
theorem relaxed_procedure {m n : ℕ} (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) :
(∃ D : ℕ → Option (Fin n → Fin m), IsAepsProcedure P ε V D) ∧
∀ D : ℕ → Option (Fin n → Fin m), IsAepsProcedure P ε V D →
IsRelaxedDecisionProcedure P (1 + ε) D := by sorry
end UnrelatedSched.FixedMachines
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.