Eqs. (6)–(8) — E[w(V_1 ∪ C)] ≤ w(V_1) + (1 − k/t)w(V_{1/2}) ≤ 2(1 − k/t)(w(V_1) + ½w(V_{1/2})) ≤ (2 − 2/(t/k)) OPT
ProvedSingleMachinePrec.Framework.eqs_6_8approximationlp-roundingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1vertex-cover
Let be an instance of whose precedence order is not a linear order, let be a -realizer of , and let be a half-integral optimal solution of [CS-LP], with . For each let , where is the set of pairs of reversed in . Then
where is the minimum weight of a vertex cover of .
This chain is the cost estimate of Theorem 5.1. Step (7) uses , which holds because is not a linear order; step (8) uses that is the optimal value of [CS-LP].
Formalization Note The expectation is the uniform average over the indices. The paper's assumption is stated as " is not a linear order" (equivalent by p. 655). and are real divisions.
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_Framework_CSLP
Formal statement
namespace SingleMachinePrec.Framework
/-- **Eqs. (6)–(8)** (p. 659). Let `P` (the precedence order of `S`) not be a linear order, let
`L_1, …, L_t` be a `k : t`-realizer of `P`, and let `x` be a half-integral optimal solution of
[CS-LP]. With `C_i = V_1 ∪ (V_{1/2} \ I_{1/2}(L_i))`:
(6) `(1/t) ∑_i w(C_i) ≤ w(V_1) + (1 - k/t) w(V_{1/2})`;
(7) `w(V_1) + (1 - k/t) w(V_{1/2}) ≤ 2 (1 - k/t) (w(V_1) + ½ w(V_{1/2}))`;
(8) `2 (1 - k/t) (w(V_1) + ½ w(V_{1/2})) ≤ (2 - 2/(t/k)) · OPT`. -/
theorem eqs_6_8 {N : Type*} [Fintype N] [DecidableEq N] (S : Instance N)
(hP : ¬ IsLinearOrder N S.P) (k t : ℕ)
(L : Fin t → LinearExtension S.P) (hL : IsKFoldRealizer S.P k t L)
(x : IncPair S.P → ℝ) (hx : IsCSLPOptimal S x) (hhalf : IsHalfIntegral x) :
(1 / (t : ℝ)) * ∑ i, weight S (roundedCover x (L i)) ≤
weight S (levelSet x 1) + (1 - (k : ℝ) / t) * weight S (levelSet x (1 / 2)) ∧
weight S (levelSet x 1) + (1 - (k : ℝ) / t) * weight S (levelSet x (1 / 2)) ≤
2 * (1 - (k : ℝ) / t) *
(weight S (levelSet x 1) + 1 / 2 * weight S (levelSet x (1 / 2))) ∧
2 * (1 - (k : ℝ) / t) *
(weight S (levelSet x 1) + 1 / 2 * weight S (levelSet x (1 / 2))) ≤
(2 - 2 / ((t : ℝ) / k)) * OPT S := by sorry
end SingleMachinePrec.Framework
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 659, Eqs. (6), (7), (8) (proof of Theorem 5.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.