neal young / Khuller96Low

SIAM Journal on Computing 25(2):355368(1996); STOC'94The degreed spanning tree problem asks for a minimumweight spanning tree in which the degree of each vertex is at most $d$. When $d=2$ the problem is TSP, and in this case, the wellknown Christofides algorithm provides a 1.5approximation algorithm (assuming the edge weights satisfy the triangle inequality).
Christos Papadimitriou and Umesh Vazirani posed the challenge of finding an algorithm with performance guarantee less than 2 for Euclidean graphs (points in $R^n$) and $d > 2$ [1984]. This paper gives the first answer to that challenge, presenting an algorithm to compute a degree3 spanning tree of cost at most 5/3 times the MST. For points in the plane, the ratio improves to 3/2 and the algorithm can also find a degree4 spanning tree of cost at most 5/4 times the MST.Journal version of [1994].
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.