Abstract:
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. 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 defined as follows. Given a weighted undirected graph with degree bound B, the task is to find a spanning tree of minimum cost that satisfies the degree bound. We present a polynomial time algorithm that returns a spanning tree of optimal cost and maximum degree B+1. This generalizes a result of Furer and Raghavachari to weighted graphs, and thus settles a 15-year-old conjecture of Goemans affirmatively. This is also the best possible result for the problem in polynomial time unless P=NP.
We also study degree bounded versions of general network design problems including the minimum bounded degree Steiner tree problem, the minimum bounded degree Steiner forest problem, minimum bounded degree k-edge connected subgraph problem and the minimum bounded degree arborescence problem. We show that iterative methods give bi-criteria approximation algorithms that return a solution whose cost is within a small constant factor of the optimal solution and the degree bounds are violated by an additive factor in undirected graphs and a small multiplicative factor in directed graphs. These results also imply first additive approximation algorithms for various degree constrained network design problems in undirected graphs.
We also show the generality of the iterative methods and apply it to degree constrained matroid problem, multi-criteria spanning tree problem, multi-criteria matroid basis problem and the generalized assignment problem achieving or matching best known approximation algorithms for them.