Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

作者：Singh Mohit^*; Lau Lap Chi

来源：Journal of the ACM, 2015, 62(1): 1.

DOI：10.1145/2629366

• Algorithms
• Theory
• Approximation algorithms
• spanning trees
• bounded degree
• iterative rounding

In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected graph G = (V, E) with a degree upper bound B-v on each vertex v is an element of 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 T of cost at most OPT and d(T) (v) <= B-v + 1 for all v, where d(T) (v) denotes the degree of v in T. This generalizes a result of Furer and Raghavachari [1994] to weighted graphs, and settles a conjecture of Goemans [2006] affirmatively. The algorithm generalizes when each vertex v has a degree lower bound A(v) and a degree upper bound Bv, and returns a spanning tree with cost at most OPT and A(v) -1 <= d(T) (v) <= Bv + 1 for all v is an element of V. This is essentially the best possible. The main technique used is an extension of the iterative rounding method introduced by Jain [2001] for the design of approximation algorithms.

• 出版日期2015-2
• 单位Microsoft; 香港中文大学（深圳）