Approximating the Degree-Bounded Minimum-Diameter Spanning Tree Problem

maximum node degree $B$ in a complete undirected edge-weighted graph. We
prove that the problem is NP-complete, and provide an
$O(\sqrt{\log_Bn})$-approximation algorithm for the problem. Our algorithm
is purely combinatorial, and relies on a combination of {\em filtering}
and divide and conquer.

This is joint work with Asaf Levin at Tel-Aviv University and
Amitabh Sinha at CMU.