CombOpt ReadingGroup - Sina Kalantarzadeh-Minimum Bounded Degree Spanning Trees

Abstract: I will present Goemans’s beautiful, though no longer state-of-the-art, 2006 result on the Minimum Bounded-Degree Spanning Tree problem. Given a weighted graph (G=(V,E)) and degree bounds (B\to\mathbb{N}), the goal is to find a minimum-cost spanning tree (T) satisfying (d_T(v)\le B(v)) for every (v\in V). This problem is NP-hard. Fürer and Raghavachari (1992) gave a polynomial-time algorithm for the unweighted setting that produces a spanning tree satisfying (d_T(v)\le B(v)+1). For the weighted problem, Goemans designed an elegant LP-rounding algorithm that returns a tree of cost at most that of the optimal degree-bounded solution while satisfying (d_T(v)\le B(v)+2). I will explain this result and the simple yet beautiful combinatorial optimization ideas underlying it. In 2007, Singh and Lau improved the violation to (B(v)+1) using iterative relaxation, which I might give a talk about in later sessions.