Paper Info
Title
Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
Abstract
We present a new bicriteria approximation algorithm for the degree-bounded minimum-cost spanning tree (MST) problem: Given an undirected graph with nonnegative edge weights and a degree bound B, find a spanning tree of maximum node-degree B and minimum total edge-cost. Our algorithm outputs a tree of maximum degree at most a constant times B and total edge-cost at most a constant times that of a minimum-cost degree-B-bounded spanning tree.While our new algorithm is based on ideas from Lagrangian relaxation, as is our previous work [SIAM J. Comput., 31 (2002), pp. 1783--1793], it does not rely on computing a solution to a linear program. Instead, it uses a repeated application of Kruskal's MST algorithm interleaved with a combinatorial update of approximate Lagrangian node-multipliers maintained by the algorithm. These updates cause subsequent repetitions of the spanning tree algorithm to run for longer and longer times, leading to overall progress and a proof of the performance guarantee. A second useful feature of our algorithm is that it can handle nonuniform degree bounds on the nodes: Given distinct bounds Bv for every node $v \in V$, the output tree has degree at most O(Bv + log|V|) for every $v \in V$. As before, the cost of the tree is at most a constant times that of a minimum-cost tree obeying all degree bounds.
Year
DOI
Venue
2005
10.1137/S0097539702418048
SIAM J. Comput.
Keywords
Field
DocType
minimum-cost tree,maximum degree,new bicriteria approximation algorithm,approximating msts,nonuniform degree bound,degree bound,mst algorithm,tree algorithm,constant time,new algorithm,nonuniform degree bounds,output tree,primal-dual meets local search,linear program,spanning trees,local search,lagrangian relaxation,approximation algorithms,spanning tree
Discrete mathematics,Combinatorics,Distributed minimum spanning tree,Prim's algorithm,k-minimum spanning tree,Spanning tree,Gomory–Hu tree,Mathematics,Kruskal's algorithm,Reverse-delete algorithm,Minimum spanning tree
Journal
Volume
Issue
ISSN
34
3
0097-5397
ISBN
Citations 
PageRank 
1-58113-674-9
33
1.72
References 
Authors
8
2
Name
Order
Citations
PageRank
Jochen Könemann11589.98
R. Ravi22898275.40