### Approximating Minimum Bounded Degree Spanning Trees to within One of OptimalApproximating Minimum Bounded Degree Spanning Trees to within One of Optimal Access Restriction
Subscribed

 Author Singh, Mohit ♦ Lau, Lap Chi Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Approximation algorithms ♦ Bounded degree ♦ Iterative rounding ♦ Spanning trees Abstract In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected graph $\textit{G}$ = (V, E) with a degree upper bound $B_{v}$ on each vertex $\textit{v}$ ∈ $\textit{V},$ and the task is to find a spanning tree of minimum cost that satisfies all the degree bounds. Let OPT be the cost of an optimal solution to this problem. In this article we present a polynomial-time algorithm which returns a spanning tree $\textit{T}$ of cost at most OPT and $d_{T}(v)$ ≤ $B_{v}$ + 1 for all $\textit{v},$ where $d_{T}(v)$ denotes the degree of $\textit{v}$ in $\textit{T}.$ This generalizes a result of Fürer and Raghavachari  to weighted graphs, and settles a conjecture of Goemans  affirmatively. The algorithm generalizes when each vertex $\textit{v}$ has a degree lower bound $A_{v}$ and a degree upper bound $B_{v},$ and returns a spanning tree with cost at most OPT and $A_{v}$ - 1 ≤ $d_{T}(v)$ ≤ $B_{v}$ + 1 for all $\textit{v}$ ∈ $\textit{V}.$ This is essentially the best possible. The main technique used is an extension of the iterative rounding method introduced by Jain  for the design of approximation algorithms. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-03-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 1 Page Count 19 Starting Page 1 Ending Page 19

#### Open content in new tab

Source: ACM Digital Library