Iterative Methods in Combinatorial Optimization

Linear programming has been a successful tool in combinatorial optimization to achieve good approximation algorithms for problems which are NP-hard. In this thesis, 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, 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 settles a 15-year-old conjecture of Goemans affirmatively. This is essentially the best possible result for this problem. We also obtain strong bi-criteria approximation algorithms for degree constrained versions of general network design problems. For the Minimum bounded degree Survivable network design problem, we give an algorithm which returns a solution with cost at most twice the optimal cost and the degree bound is violated by an additive term. This result, as a corollary, implies first additive approximation algorithms for a large class of degree constrained network design problems including bounded degree Steiner Forest problem and bounded k-edge connected subgraph problem.

These results add to a rather small list of problems, edge coloring, coloring planar graphs, degree constrainted Steiner trees, where additive approximation algorithms are known. As a byproduct of our results, we also obtain new proofs of integrality of linear programming relaxations for a large class of combinatorial optimization problems including spanning trees, bipartite matching, perfect matching in general graphs, Matroids, Matroid intersection, Submodular flows etc. Apart from degree constrained problems, the integrality results can be extended to obtain approximation algorithms for constrained problems in Matroids and Submodular flows, scheduling on unrelated parallel machines and multi-criteria problems thus providing a unifying framework to obtain approximation algorithms for a large class of combinatorial optimization problems.