Theorem 5.2 — MBDCT Algorithm2 is a (1, A_v − 1, B_v + 1)-approximation for the minimum bounded degree connecting tree problem
ProvedBoundedDegreeST.LowerUpper.theorem_5_2Let be a finite simple graph with edge costs of any sign, a forest on with , and let () and () be integer lower and upper degree bounds. An -tree is a set such that is a spanning tree, and is the number of edges of at . Assume LP-MBDCT is feasible. Then MBDCT Algorithm2 (Figure 5) satisfies:
- (a run exists) some run returns a set ;
- (iteration bound) every run makes at most iterations;
- (guarantee) every returned is an -tree in with
At this returns a spanning tree of cost at most OPT with , the paper's abstract claim for the problem with both lower and upper bounds.
Formalization Note "There is a polynomial time -approximation algorithm" is made explicit as (1)–(3) for the algorithm of Figure 5 quantified over every choice it leaves open; "polynomial time" is the iteration bound, with the LP solved by an oracle (any basic optimal solution), and the ellipsoid/separation running time is not modelled. "Cost at most the LP optimum" is for every feasible . LP feasibility is an explicit hypothesis. Step 4 carries the guard "no 1-edge" stated in the paper's text under Lemma 5.1 (see the Algorithm definition).
import Definitions.Def_BoundedDegreeST_LowerUpper_Algorithm
namespace BoundedDegreeST.LowerUpper
/-- Singh–Lau, Theorem 5.2, p. 668: MBDCT Algorithm2 is a
`(1, A_v − 1, B_v + 1)`-approximation for the minimum bounded degree connecting
tree problem. On a well-formed instance whose LP is feasible:
(1) some run returns; (2) every run makes at most `|V| − |F| − 1 + |U ∪ W|`
iterations (the LP is solved by an oracle); (3) every returned `H` is an
`F`-tree in `E` with `c(H)` at most the BoundedDegreeST.PlusOne.cost of every feasible LP solution
and `A_v − 1 ≤ d_H(v)` on `U`, `d_H(v) ≤ B_v + 1` on `W`. -/
theorem theorem_5_2 {V : Type*} [Fintype V] [DecidableEq V]
(c : Sym2 V → ℝ) (I : Instance V)
(hvalid : Valid I) (hfeasible : ∃ x, Feasible I.E I.A I.B I.U I.W I.F x) :
(∃ H, Returns c I H) ∧
(∀ k, Chain c I k →
(k : ℤ) ≤ (Fintype.card V : ℤ) - (I.F.card : ℤ) - 1 + ((I.U ∪ I.W).card : ℤ)) ∧
(∀ H, Returns c I H →
H ⊆ I.E ∧ BoundedDegreeST.PlusOne.IsSpanningTree (H ∪ I.F) ∧
(∀ x, Feasible I.E I.A I.B I.U I.W I.F x →
BoundedDegreeST.PlusOne.cost c H ≤ ∑ e ∈ I.E, c e * x e) ∧
(∀ v ∈ I.U, I.A v - 1 ≤ (degree H v : ℤ)) ∧
(∀ v ∈ I.W, (degree H v : ℤ) ≤ I.B v + 1)) := by sorry
end BoundedDegreeST.LowerUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.