§7, proof of Theorem 7.2, p. 33 — second L-reduction condition: OPT_SAT(I) − #(SAT(S)) ≤ VAL(S) − OPT_SCH(R(I))
ProvedSkutellaCQP.MaxSNP.l_condition_2l-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 . For every feasible schedule of ,
where .
This is the second condition of an L-reduction with constant : the loss of the truth assignment recovered from a schedule is at most the excess of the schedule over the optimum.
Formalization Note " optimal" is the pair of hypotheses: is feasible, and for every feasible . The inequality is stated over the reals.
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_MaxSNP_Setting
Formal statement
namespace SkutellaCQP.MaxSNP
/-- Proof of Theorem 7.2 (p. 33), second L-reduction condition: for an optimal schedule `S₀` and
every feasible schedule `S` of `R(I)`, `OPT_SAT(I) − #(SAT(S)) ≤ VAL(S) − OPT_SCH(R(I))`. -/
theorem l_condition_2 {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)
(S : Sched n m) (hS : Feasible I S) :
(optSat I : ℝ) - satCount I (SAT 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, §7, proof of Theorem 7.2, second display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.