Theorem 6.1, p. 30 — for ρ ≤ 1, an m-cut of weight ≥ ρ·Z*_cut gives a schedule within ρ + m(1 − ρ) of optimal for Pm | | Σ wⱼCⱼ
ProvedSkutellaCQP.MaxCut.theorem_6_1Consider jobs with processing times and weights on identical parallel machines, Smith's order , and the weighted complete graph with for . Let , and let be an assignment of the jobs to the machines whose induced -cut has weight at least times the weight of every -cut of , i.e. . Then the schedule that uses as its machine assignment and sequences each machine by satisfies
that is, its value is at most .
This is the paper's Theorem 6.1: a -approximation algorithm for Max--Cut, applied to , translates into an approximation algorithm for with performance guarantee .
Formalization Note The algorithmic content ("translates into an approximation algorithm") is the map from cut to assignment, which is the identity on partitions; the running time is not formalized. "Weight at least " is written as for every assignment , and as the value of every assignment, so no maximum or minimum is a primitive.
import Mathlib import Definitions.Def_SkutellaCQP_MaxCut_Setting
namespace SkutellaCQP.MaxCut
open Finset
/-- Theorem 6.1, p. 30. Let `ρ ≤ 1`. If the assignment `σ` induces an `m`-cut of `G_J` whose weight
is at least `ρ` times the weight of every `m`-cut (i.e. at least `ρ · Z*_cut`), then the schedule
of `σ` has value at most `ρ + m(1 − ρ)` times the value of every schedule. -/
theorem theorem_6_1 {m n : ℕ} (p w : Fin n → ℝ) (hp : ∀ j, 0 < p j) (hw : ∀ j, 0 ≤ w j)
(hm : 0 < m) (ρ : ℝ) (hρ : ρ ≤ 1) (σ : Fin n → Fin m)
(hσ : ∀ τ : Fin n → Fin m, ρ * cut p w τ ≤ cut p w σ) :
∀ τ : Fin n → Fin m, val p w σ ≤ (ρ + m * (1 - ρ)) * val p w τ := by sorry
end SkutellaCQP.MaxCut
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.