Lemma 2.8 and Corollary 2.9, pp. 13–14 — (CQP′) contains every schedule, and rounding any feasible (ā, Z) has expected value ≤ 3/2 · Z
ProvedSkutellaCQP.NoRel.three_halves_roundingConsider an instance of with processing times and weights , and the convex relaxation (CQP′):
Then:
- (CQP′) is a relaxation. For every assignment of jobs to machines (each machine sequenced by Smith's order), its vector together with is feasible for (CQP′). Hence .
- Lemma 2.8. For every feasible of (CQP′), Algorithm RANDOMIZED ROUNDING (each job to machine with probability , choices pairwise independent) produces a schedule with
Together the two parts say that the optimal schedule value is within a factor of the optimum of (CQP′) (Corollary 2.9), and that rounding a (near-)optimal solution of (CQP′) yields a randomized -approximation for .
Formalization Note The first conjunct is what makes a lower bound on the optimum; without it the bound of the second would be against an arbitrary number. Polynomial-time solvability of (CQP′) within additive error and derandomization are not formalized. The rounding is any probability weight on assignments with the prescribed one- and two-job marginals (pairwise independence).
import Mathlib import Definitions.Def_SkutellaCQP_NoRel_Setting
namespace SkutellaCQP.NoRel
/-- Goal: Corollary 2.9 (relaxation half) and Lemma 2.8 (pp. 13–14).
(1) Every assignment `σ`, with `Z` its value `∑_j w_j C_j`, is feasible for (CQP′), so the optimum of
(CQP′) is at most the optimal schedule value.
(2) For any feasible `(a, Z)` of (CQP′), randomized rounding with pairwise independent choices yields
a schedule of expected value at most `3/2 · Z`. -/
theorem three_halves_rounding {m n : ℕ} (p : Fin m → Fin n → ℝ) (w : Fin n → ℝ)
(hp : ∀ i j, 0 < p i j) (hw : ∀ j, 0 ≤ w j) :
(∀ σ : Fin n → Fin m, CQP'Feasible p w (ind σ) (val p w σ)) ∧
∀ (a : Fin m → Fin n → ℝ) (Z : ℝ), CQP'Feasible p w a Z →
∀ μ : (Fin n → Fin m) → ℝ, IsPairwiseRounding a μ → E μ (val p w) ≤ (3 / 2) * Z := by sorry
end SkutellaCQP.NoRel
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.