(38), p. 31 — Z*_cut ≤ (m − 1)/m · c(E_J) + (1/2 − 1/(2m)) Σⱼ wⱼpⱼ
ProvedSkutellaCQP.MaxCut.eq_38identical-machinesmax-k-cutp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1upper-bound
Consider jobs with processing times and weights on identical parallel machines and the weighted complete graph of total weight . Every -cut of , induced by a partition of the jobs, has weight
In particular this bounds the weight of a maximum -cut.
The bound compares the maximum cut with the scheduling optimum and is the step that turns a -approximate cut into an approximate schedule in Theorem 6.1.
Formalization Note is not a primitive; the bound is stated for every partition, which is equivalent because there are finitely many.
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_MaxCut_Setting
Formal statement
namespace SkutellaCQP.MaxCut
open Finset
/-- Display (38), §6, proof of Theorem 6.1, p. 31. Every `m`-cut of `G_J` (hence a maximum one,
`Z*_cut`) weighs at most `(m − 1)/m · c(E_J) + (1/2 − 1/(2m)) ∑_j w_j p_j`. -/
theorem eq_38 {m n : ℕ} (p w : Fin n → ℝ) (hp : ∀ j, 0 < p j) (hw : ∀ j, 0 ≤ w j) (hm : 0 < m) :
∀ τ : Fin n → Fin m,
cut p w τ ≤ ((m : ℝ) - 1) / m * cE p w + (1 / 2 - 1 / (2 * (m : ℝ))) *
∑ j, w j * p j := by sorry
end SkutellaCQP.MaxCut
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 31, §6, proof of Theorem 6.1, display (38)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.