Speaker: Mohit Singh
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Delegate and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs
The minimum spanning tree problem is a fundamental problem in combinatorial optimization. It also has various applications, especially in network design. A favorable property of a connecting network is not only to be ‘cheap’ but also to have ’small load’ on all nodes. A natural way to formulate this problem is via the minimum degree minimum spanning tree (MDMST) problem.
In an instance of the MDMST problem, we are given a graph G=(V,E) and a non-negative cost function c on edges, and the objective is to find a minimum cost spanning tree T under the cost function c such that maximum degree of T is minimized. Here, the maximum degree of T is the maximum degree among all vertices in T.
In this talk, we will present an algorithm for the MDMST problem which returns a MST of maximum degree at most OPT+k where OPT is the minimum maximum degree of any MST and k is the distinct number of costs in any MST of G. We use a lower bound given by a linear programming relaxation to the problem and strengthen known graph-theoretic results on minimum degree subgraphs to prove our result.
This is joint work with R. Ravi.
