Theorem 8.1 — approximating the variable cost of is as hard as approximating vertex cover
ProvedSingleMachinePrec.VariableCost.theorem_8_1Let be a graph on vertices , with vertex cover number . Let and , and let satisfy
Let be the scheduling instance of the proof of Theorem 8.1, and let be the minimum weight of a vertex cover of its vertex cover graph (the optimal variable cost). Let be a vertex cover of with , and put
Then:
- is a vertex cover of ;
- ;
- if , then
The paper states: "Approximating the variable cost of is as hard as approximating vertex cover", and concludes that an -approximation algorithm for the variable cost would give an approximation algorithm for vertex cover with ratio . Its proof establishes the statement above, which is what is formalized: any -approximate solution of the variable-cost problem on is turned, by the explicit map , into an -approximate vertex cover of . Together with Theorem 2.1 of the paper (cited from Ambühl–Mastrolilli and Correa–Schulz: an -approximate vertex cover of can be turned in polynomial time into an -approximate solution of ), this shows that the variable cost is no easier to approximate than vertex cover.
Formalization Note The algorithmic wording ("approximation algorithm", polynomial time) and the cited Theorem 2.1 are not formalized; the size of (polynomial in and ) is evident from the definition. The hypothesis is implicit on the page: "" does not imply it when is large. The additive bound (2) is stated for every graph, and the multiplicative bound (3) only when has an edge, since otherwise and the strict inequality fails. is Mathlib's vertexCoverNum, an extended natural number that is finite for a finite graph, converted with toNat.
import Mathlib import Definitions.Def_SingleMachinePrec_VariableCost_AdjacencyInstance open scoped NNReal
namespace SingleMachinePrec.VariableCost
open Classical in
/-- Theorem 8.1 (p. 664): approximating the variable cost of `1|prec|∑ w_j C_j` is as hard as
approximating vertex cover. What the proof establishes: let `G` be a graph on `n` vertices,
`r ≥ 1`, `ε > 0`, `k > n² r / ε` with `k ≥ 1`, and `S = adjacencyInstance G k`. If `C` is a
vertex cover of `G^S_P` whose weight is at most `r` times the minimum weight of a vertex cover of
`G^S_P`, then `C_G = {v_i : (v′_i, v″_i) ∈ C}` is a vertex cover of `G` with
`|C_G| ≤ r (τ(G) + n²/k)`, and, if `G` has an edge, `|C_G| ≤ r (1 + n²/k) τ(G) < (r + ε) τ(G)`,
where `τ(G)` is the vertex cover number of `G`. -/
theorem theorem_8_1 {n : ℕ} (G : SimpleGraph (Fin n)) (r ε : ℝ) (k : ℝ≥0)
(hr : 1 ≤ r) (hε : 0 < ε) (hk1 : 1 ≤ k) (hk : (n : ℝ) ^ 2 * r / ε < (k : ℝ))
(C : Finset (IncPair (adjacencyInstance G k).P))
(hC : (vertexCoverGraph (adjacencyInstance G k).P).IsVertexCover (C : Set _))
(hCr : weight (adjacencyInstance G k) C ≤ r * minCoverWeight (adjacencyInstance G k)) :
G.IsVertexCover {i | heavy G k i ∈ C} ∧
((Finset.univ.filter (fun i => heavy G k i ∈ C)).card : ℝ) ≤
r * ((G.vertexCoverNum.toNat : ℝ) + (n : ℝ) ^ 2 / (k : ℝ)) ∧
(G.edgeSet.Nonempty →
((Finset.univ.filter (fun i => heavy G k i ∈ C)).card : ℝ) ≤
r * (1 + (n : ℝ) ^ 2 / (k : ℝ)) * (G.vertexCoverNum.toNat : ℝ) ∧
r * (1 + (n : ℝ) ^ 2 / (k : ℝ)) * (G.vertexCoverNum.toNat : ℝ) <
(r + ε) * (G.vertexCoverNum.toNat : ℝ)) := by sorry
end SingleMachinePrec.VariableCost
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.