§7, p. 664 — the light nodes weigh less than 1 in total, so
ProvedSingleMachinePrec.IntervalReduction.light_weightinterval-ordersp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingvertex-cover
Let be the Stage 2 instance, with jobs and . Let be the minimum weight of a vertex cover of and the minimum size of a vertex cover of the unweighted graph induced by . Then
The weight-one nodes thus determine the optimum exactly, up to the fractional contribution of the light nodes, which the floor removes.
Formalization Note is Nat.floor, which equals the integer floor here because . The left sum ranges over all ordered incomparable pairs of that are not in .
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_IntervalReduction_Instance
Formal statement
namespace SingleMachinePrec.IntervalReduction
open Classical in
/-- §7, p. 664: with `k = n² + 1`, the incomparable pairs outside `D` have total weight
`∑_{(i,j) ∈ inc(I) \ D} p_i w_j < 1`, and therefore the minimum vertex cover of the unweighted
graph `G′_I` has size `⌊w(C_I)⌋`. -/
theorem light_weight {N : ℕ} {G : SimpleGraph (Fin N)} (L : TreeLayout G) :
(∑ u : IncPair (prec L),
if InD L u.1.1 u.1.2 then 0
else vertexWeight (prec L) (procTime L (kVal L)) (weight L (kVal L)) u) < 1 ∧
(GIprime L).vertexCoverNum = ((⌊tauW L⌋₊ : ℕ) : ℕ∞) := by sorry
end SingleMachinePrec.IntervalReduction
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 664, §7 (display following the choice k = n^2 + 1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.