Theorem 2.6 b), p. 12 — uniform independent random assignment is a (3/2 − 1/(2m))-approximation for P | | Σ wⱼCⱼ
ProvedSkutellaCQP.MaxCut.theorem_2_6_bConsider jobs with processing times and weights on identical parallel machines. Assign each job independently and uniformly at random to one of the machines, and sequence each machine by Smith's order . Every assignment then has probability , and the expected value of the schedule satisfies
for every assignment , i.e. the expectation is within a factor of the optimum .
This is the guarantee of the simplest randomized algorithm for ; it coincides with randomized rounding of the (CQP) optimum of Lemma 2.5.
Formalization Note The random assignment is the uniform distribution on the assignments, written as an explicit finite sum. is the minimum over assignments, so the bound is stated against every assignment .
import Mathlib import Definitions.Def_SkutellaCQP_MaxCut_Setting
namespace SkutellaCQP.MaxCut
open Finset
/-- Theorem 2.6 b), p. 12. Assigning each job independently and uniformly at random to one of the
`m` identical machines (each assignment `σ` has probability `(1/m)^n`) gives an expected value
`∑_j w_j C_j` at most `(3/2 − 1/(2m))` times the value of every schedule. -/
theorem theorem_2_6_b {m n : ℕ} (p w : Fin n → ℝ) (hp : ∀ j, 0 < p j) (hw : ∀ j, 0 ≤ w j)
(hm : 0 < m) :
∀ τ : Fin n → Fin m,
∑ σ : Fin n → Fin m, (1 / (m : ℝ)) ^ n * val p w σ ≤
(3 / 2 - 1 / (2 * (m : ℝ))) * val p w τ := by sorry
end SkutellaCQP.MaxCut
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.