Theorem 4.2 — connecting tree of LP cost and degree B + 1
ProvedBoundedDegreeST.PlusOne.theorem_4_2iterative-roundinglinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-trees
Let be a well-formed connecting-tree instance with a feasible LP-MBDCT solution and any real edge costs. The Figure 4 algorithm has a terminating run. Every run has at most iterations, and every returned set is an -tree drawn from with
The LP bound includes the optimum and supports the spanning-tree theorem at , .
Formalization Note LP feasibility makes the oracle step available. The theorem states run existence and a bound for every possible step chain so the return guarantee is not vacuous; it does not formalize the ellipsoid running time.
Preamble
import Definitions.Def_BoundedDegreeST_PlusOne_Algorithm
Formal statement
namespace BoundedDegreeST.PlusOne
/-- Singh–Lau, Theorem 4.2, p. 666, with the recursion and LP bound explicit. -/
theorem theorem_4_2 {V : Type*} [Fintype V] [DecidableEq V]
(c : Sym2 V → ℝ) (I : Instance V)
(hvalid : Valid I) (hfeasible : ∃ x, Feasible I.E I.B I.W I.F x) :
(∃ H, Returns c I H) ∧
(∀ k, Chain c I k →
(k : ℤ) ≤ (Fintype.card V : ℤ) - (I.F.card : ℤ) - 1 + (I.W.card : ℤ)) ∧
(∀ H, Returns c I H →
H ⊆ I.E ∧ IsSpanningTree (H ∪ I.F) ∧
(∀ v ∈ I.W, (degree H v : ℤ) ≤ I.B v + 1) ∧
(∀ x, Feasible I.E I.B I.W I.F x →
cost c H ≤ ∑ e ∈ I.E, c e * x e)) := by sorry
end BoundedDegreeST.PlusOne
Source
Singh, Lau, Approximating minimum bounded degree spanning trees to within one of optimal, STOC 2007, p. 666, Theorem 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.