(36), p. 30 — c(E_J) = Σⱼ wⱼCⱼ − Σⱼ wⱼpⱼ + c(E_cut) for every partition of J into m machines
ProvedSkutellaCQP.MaxCut.eq_36Consider jobs with processing times and weights on identical parallel machines, Smith's order , and the weighted complete graph with for . Let be any assignment of the jobs to the machines (a partition ), let be the completion times of the schedule that sequences each machine by , and let be the -cut induced by the partition. Then
The value of a schedule is the weight of the edges inside the parts plus the constant . Since and do not depend on , minimizing is the same as maximizing the weight of the induced -cut; this is the reduction of to Max--Cut.
Formalization Note The identity holds for any real data; the standing hypotheses , , are kept for uniformity with the other statements of the mission.
import Mathlib import Definitions.Def_SkutellaCQP_MaxCut_Setting
namespace SkutellaCQP.MaxCut
open Finset
/-- Display (36), §6, p. 30. For every partition of the jobs `J` into `m` subsets, given by an
assignment `σ`, the total weight of `G_J` equals the value of the corresponding schedule minus
`∑_j w_j p_j` plus the weight of the induced `m`-cut:
`c(E_J) = ∑_j w_j C_j − ∑_j w_j p_j + c(E_cut)`. -/
theorem eq_36 {m n : ℕ} (p w : Fin n → ℝ) (hp : ∀ j, 0 < p j) (hw : ∀ j, 0 ≤ w j) (hm : 0 < m) :
∀ σ : Fin n → Fin m, cE p w = val p w σ - ∑ j, w j * p j + cut p w σ := by sorry
end SkutellaCQP.MaxCut
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.