Iterative Methods in Combinatorial Optimization

Monday, October 1, 2007 - 4:30pm
Mohit Singh
Tepper School of Business, Carneigie Mellon University

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. 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 talk, 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 such that 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 using the iterative method.