Lemma 3.7 — an -colourable graph gives a schedule of S(r, d) with makespan
ProvedFlowJobHardness.ColoringReduction.lemma_3_7completenessflow-shopgraph-coloringjob-shopp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a simple graph on vertices with a proper colouring into classes, let , and let be the generalized flow shop instance of the colouring reduction, with .
If the vertices of can be coloured properly with colours, then has a feasible schedule of all its jobs with makespan
This is the completeness half of the reduction: a graph of small chromatic number yields an instance with a short schedule.
Formalization Note. The paper's hypothesis is stated as -colourability (G.Colorable L), which is all the proof uses and includes the case . "A schedule with makespan " is read as makespan at most ; the paper's own schedule ends at or before that time.
Preamble
import Mathlib import Definitions.Def_JobShopLTAS_Core_Instance import Definitions.Def_FlowJobHardness_ColoringReduction_Construction import Definitions.Def_FlowJobHardness_ColoringReduction_Schedule open JobShopLTAS.Core
Formal statement
namespace FlowJobHardness.ColoringReduction
/-- **Lemma 3.7** (Mastrolilli–Svensson 2011, p. 20:17). If `G` can be coloured with `L`
colours (`χ(G) = L` in the paper), then `S(r, d)` has a feasible schedule with makespan at most
`lb · 2L = 2L · r^{2d}`. -/
theorem lemma_3_7 {n d : ℕ} (G : SimpleGraph (Fin n)) (c : G.Coloring (Fin d)) (r : ℕ)
(L : ℕ) (hL : G.Colorable L) :
∃ s : (inst G c r).Op → ℝ,
(inst G c r).IsFeasibleSchedule Finset.univ s ∧
(inst G c r).makespan Finset.univ s ≤ 2 * (L : ℝ) * (R r d : ℝ) := by sorry
end FlowJobHardness.ColoringReduction
Source
Mastrolilli, Svensson, Hardness of Approximating Flow and Job Shop Scheduling Problems, J. ACM 58(5) (2011), Article 20, p. 20:17, Lemma 3.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.