Speaker: Mohit Singh
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Delegate and Conquer: An LP-based approximation algorithm for
Minimum Degree MSTs
Abstract:
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.