§8, p. 664 — heavy nodes have weight 1, light nodes weight at most 1/k, total light weight at most n²/k
ProvedSingleMachinePrec.VariableCost.light_vertices_weightp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionsschedulingvertex-cover
Let be a graph on vertices , let , and let be the scheduling instance of the proof of Theorem 8.1, with vertex cover graph and node weights . Call the nodes heavy and all other nodes light. Then:
- every heavy node has weight ;
- every light node has weight ;
- the total weight of the light nodes satisfies
These bounds say that, up to an additive , the weight of a vertex cover of is the number of heavy nodes it contains.
Formalization Note The page also says that "has at most vertices". That is false as printed: the pairs and with are incomparable nodes of weight , so the graph can have up to nodes. Only the weight facts, which the argument uses, are formalized. The hypothesis is implicit on the page (for the light nodes would be heavier than ).
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_VariableCost_AdjacencyInstance open scoped NNReal
Formal statement
namespace SingleMachinePrec.VariableCost
open Classical in
/-- §8, p. 664 (proof of Theorem 8.1). For the instance `S = adjacencyInstance G k` with
`k ≥ 1`: every node `(v′_i, v″_i)` of `G^S_P` has weight `1`; every other node has weight at
most `1/k`; and the total weight of the other ("light") nodes is at most `n²/k`. -/
theorem light_vertices_weight {n : ℕ} (G : SimpleGraph (Fin n)) (k : ℝ≥0) (hk : 1 ≤ k) :
(∀ i : Fin n, vertexWeight (adjacencyInstance G k) (heavy G k i) = 1) ∧
(∀ u : IncPair (adjacencyInstance G k).P, (∀ i : Fin n, u ≠ heavy G k i) →
vertexWeight (adjacencyInstance G k) u ≤ 1 / (k : ℝ)) ∧
weight (adjacencyInstance G k)
(Finset.univ.filter (fun u => ∀ i : Fin n, u ≠ heavy G k i)) ≤
(n : ℝ) ^ 2 / (k : ℝ) := by sorry
end SingleMachinePrec.VariableCost
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 664, §8, proof of Theorem 8.1 (weights of G^S_P)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.