§7, proof of Theorem 7.2, p. 33 — first L-reduction condition: OPT_SCH(R(I)) ≤ 12m + 4m ≤ 32 OPT_SAT(I)
ProvedSkutellaCQP.MaxSNP.l_condition_1l-reductionmax-3-satp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingtotal-completion-time
Let be an instance of 3-OCCURRENCE MAX3SAT with variables and clauses, let be the scheduling instance constructed from it, and let be an optimal schedule of , so . Then
This is the first condition of an L-reduction (Papadimitriou–Yannakakis 1991) with constant : the optimum of the target instance is bounded by a constant times the optimum of the source instance.
Formalization Note " optimal" is the pair of hypotheses: is feasible, and for every feasible . Both inequalities of the display are stated.
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_MaxSNP_Setting
Formal statement
namespace SkutellaCQP.MaxSNP
/-- Proof of Theorem 7.2 (p. 33), first L-reduction condition: for an optimal schedule `S₀` of
`R(I)`, `OPT_SCH(R(I)) = VAL(S₀) ≤ 12m + 4m ≤ 32 · OPT_SAT(I)`. -/
theorem l_condition_1 {n m : ℕ} (I : Occ3Max3Sat n m) (hI : I.IsValid)
(S₀ : Sched n m) (hS₀ : Feasible I S₀) (hopt : ∀ S, Feasible I S → VAL S₀ ≤ VAL S) :
VAL S₀ ≤ 12 * m + 4 * m ∧ (12 * m + 4 * m : ℝ) ≤ 32 * optSat I := by sorry
end SkutellaCQP.MaxSNP
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 33, §7, proof of Theorem 7.2, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.