Low-Degree Spanning Trees of Small Weight
<|reference_start|>Low-Degree Spanning Trees of Small Weight: The degree-d spanning tree problem asks for a minimum-weight 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 well-known Christofides algorithm provides a 1.5-approximation algorithm (assuming the edge weights satisfy the triangle inequality).   In 1984, 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. This paper gives the first answer to that challenge, presenting an algorithm to compute a degree-3 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 degree-4 spanning tree of cost at most 5/4 times the MST.<|reference_end|>
@article{khuller2002low-degree,
    title={Low-Degree Spanning Trees of Small Weight},
    author={Samir Khuller, Balaji Raghavachari, Neal E. Young},
    journal={SIAM J. Computing 25(2):355-368 (1996)},
    year={2002},
    doi={10.1137/S0097539794264585},
    archivePrefix={arXiv},
    eprint={cs/0205043},
    primaryClass={cs.DS cs.DM}
}