Lemma 7.1 b), p. 33 — OPT_SCH(R(I)) = 4n + 4m − OPT_SAT(I)
ProvedSkutellaCQP.MaxSNP.lemma_7_1_bl-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, and let be the scheduling instance constructed from it. Then has an optimal schedule, and the optimal values of and of are related by
where is the minimum total completion time of a feasible schedule and is the maximum number of clauses satisfied by a truth assignment.
Together with part a) this identifies the scheduling optimum with the satisfiability optimum up to the affine map .
Formalization Note is not a primitive: the statement asserts a feasible schedule with and for every feasible . The existence of an optimal schedule is part of the page's claim (it speaks of "the values of optimal solutions").
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_MaxSNP_Setting
Formal statement
namespace SkutellaCQP.MaxSNP
/-- Lemma 7.1 b) (p. 33). `R(I)` has an optimal schedule, and its value is
`OPT_SCH(R(I)) = 4n + 4m − OPT_SAT(I)`. -/
theorem lemma_7_1_b {n m : ℕ} (I : Occ3Max3Sat n m) (hI : I.IsValid) :
∃ S₀ : Sched n m, Feasible I S₀ ∧ VAL S₀ = (4 * n + 4 * m : ℝ) - optSat I ∧
∀ S, Feasible I S → VAL S₀ ≤ VAL S := by sorry
end SkutellaCQP.MaxSNP
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 33, Lemma 7.1 b)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.