Approximating minimum bounded degree spanning trees to within one of optimal
Approximating minimum bounded degree spanning trees to within one of optimal
复制标题
DOI：
10.1145/1250790.1250887
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
Mohit Singh;L. Lau
中科院分区：
文献类型：
--
作者：
Mohit Singh;L. Lau
在最小有界度生成树问题中，我们给出了一个在每个顶点v上有度上界Bv的无向图，任务是找到一棵满足所有度上界的最小代价生成树。假设OPT是这个问题的最优解决方案的成本。本文给出了一个多项式时间算法，它对所有的v都返回最多Cost的生成树T和DT(V)≤Bv+1，其中dt(V)表示v在T中的度。这将Furer和Raghavachari[8]的一个结果推广到赋权图上，肯定地解决了Goemans[10]的一个15年猜想。该算法推广了当每个顶点v都有一个度下界Av和一个度上界Bv时，返回所有v的代价至多为opt和Av-1≤dt(V)≤Bv+1的生成树，这基本上是最好的。所使用的主要技术是Jain[12]为设计逼近算法而引入的迭代边界方法的扩展。
In the Minimum Bounded Degree Spanning Tree problem, we aregiven an undirected graph with a degree upper bound Bv on eachvertex v, and the task is to find a spanning tree of minimumcost which satisfies all the degree bounds. Let OPT be the costof an optimal solution to this problem. In this paper, we presenta polynomial time algorithm which returns a spanning tree T ofcost at most OPT and dT(v) ≤ Bv+1 for all v, where dT(v) denotes the degree of v in T. This generalizes aresult of Furer and Raghavachari [8] to weighted graphs, andsettles a 15-year-old conjecture of Goemans [10] affirmatively. The algorithm generalizes when each vertex v hasa degree lower bound Av and a degree upper bound Bv, andreturns a spanning tree with cost at most OPT and Av - 1 ≤dT(v) ≤ Bv + 1 for all v. This is essentially the bestpossible. The main technique used is an extension of the iterativerounding method introduced by Jain [12] for the design ofapproximation algorithms.