Mohit Singh
Iterative Methods in Combinatorial Optimization
Friday, August 31, 2007
10:30 am
259 Posner
Linear programming has been a successful tool in combinatorial optimization to achieve polynomial time algorithms for problems in P and also to achieve good approximation algorithms for problems which are NP-hard. In this thesis proposal, we demonstrate that iterative methods give a general framework to analyze linear programming formulations of combinatorial optimization problems. We show that iterative methods are well-suited for problems in P and lead to new proofs of integrality of linear programming formulations for various problems in P. This understanding provides us the basic groundwork to address various problems that are NP-hard and to achieve good approximation algorithms.
In this thesis proposal, we focus on degree bounded network design problems. The most well-studied problem in this class is the Minimum Bounded Degree Spanning Tree problem. We present a polynomial time algorithm that returns a spanning tree of optimal cost and the degree
of any vertex in the tree exceeds its degree bound by at most an additive one. This generalizes a result of Furer and Raghavachari to weighted graphs, and thus settles a 15-year-old conjecture of Goemans affirmatively. This is essentially the best possible result for this problem. For degree constrained versions of more general network design problems, we obtain strong bi-criteria approximation algorithms.
We conclude the proposal with our plans for future work in this topic. We strongly believe that iterative methods will provide us with better understanding for solving related problems such as the Single Source Unsplittable Flow problem and the prize collecting variants of different combinatorial optimization problems. We further wish to study the similarities between the Total-Dual Integrality (TDI) method and the iterative methods proposed here.
