Lemma 1 — binary search with a ρ-relaxed decision procedure is a ρ-approximation algorithm
ProvedUnrelatedSched.TwoApprox.lemma_1Let machines and jobs have processing times that are positive integers, and let be the minimum makespan. Let and let be a -relaxed decision procedure for this instance. Then the schedule output by the binary search of Lemma 1 driven by satisfies
The lemma reduces the design of a -approximation algorithm to the design of a -relaxed decision procedure, which only has to answer the decision question approximately for one deadline at a time.
Formalization Note The paper states: "If there is a polynomial -relaxed decision procedure ..., then there is a polynomial -approximation algorithm". Its proof establishes that the binary search outputs a schedule within , which is what is formalized; the polynomial running time is not. The procedure is evaluated at natural-number deadlines, which suffices because is an integer. No hypothesis is needed: when no -relaxed procedure with exists (it would have to beat the optimum at ), and when every makespan is . is the makespan of an optimal schedule σopt.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP import Definitions.Def_UnrelatedSched_TwoApprox_Algorithm
namespace UnrelatedSched.TwoApprox
open MatousekLP.Scheduling
/-- Lemma 1, p. 5: the binary search driven by a `ρ`-relaxed decision procedure outputs a schedule
of makespan at most `ρ` times the optimum. -/
theorem lemma_1 {m n : ℕ} (hm : 0 < m) (P : Matrix (Fin m) (Fin n) ℕ) (hP : ∀ i j, 0 < P i j)
(ρ : ℝ) (D : DecisionProcedure m n) (hD : IsRelaxedDecisionProcedure P ρ D)
(σopt : Fin n → Fin m) (hopt : IsOptimalSchedule (realTimes P) σopt) :
makespan (realTimes P) (binarySearch P hm D) ≤ ρ * makespan (realTimes P) σopt := by sorry
end UnrelatedSched.TwoApprox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.