(37), p. 31 — Z* ≥ Z*_CQP = 1/m · c(E_J) + (1/2 + 1/(2m)) Σⱼ wⱼpⱼ
ProvedSkutellaCQP.MaxCut.eq_37convex-quadratic-relaxationidentical-machineslower-boundmax-k-cutp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider jobs with processing times and weights on identical parallel machines, the graph of total weight , and the vector of Lemma 2.5. Then the optimum value of the relaxation (CQP) satisfies
and it is a lower bound on the value of every schedule: for every assignment of the jobs to the machines, so .
Combined with (36), this lower bound on the scheduling optimum becomes the upper bound (38) on the maximum -cut.
Formalization Note is the minimum of the value over assignments (Smith's rule, p. 7), so "" is stated against every assignment.
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_MaxCut_Setting
Formal statement
namespace SkutellaCQP.MaxCut
open Finset
/-- Display (37), §6, proof of Theorem 6.1, p. 31. The optimum value of (CQP),
attained at `ā ≡ 1/m` (Lemma 2.5), equals `1/m · c(E_J) + (1/2 + 1/(2m)) ∑_j w_j p_j`, and it is a
lower bound on the value `∑_j w_j C_j` of every schedule (`Z* ≥ Z*_CQP`). -/
theorem eq_37 {m n : ℕ} (p w : Fin n → ℝ) (hp : ∀ j, 0 < p j) (hw : ∀ j, 0 ≤ w j) (hm : 0 < m) :
ZCQP p w (abar m n) =
1 / (m : ℝ) * cE p w + (1 / 2 + 1 / (2 * (m : ℝ))) * ∑ j, w j * p j ∧
∀ τ : Fin n → Fin m, ZCQP p w (abar m n) ≤ val p w τ := 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 (37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.