Abstract :

In this talk we will demonstrate an iterative relaxation method as a framework to analyze linear programming formulations of combinatorial optimization problems. This method was first developed to tackle degree-bounded network design problems, where it gave approximation algorithms with only additive constant errors. In particular, it gave an approximation algorithm with error at most 1 for the minimum bounded degree spanning tree problem, proving a conjecture of Goemans. Then we will present the recent developments of this method. We show how this method provides new proofs of exact linear programming formulations for many classical problems, and see how these new proofs lead us to obtain new results in approximation algorithms. Finally we will discuss potential future directions of this method, and highlight some interesting open problems. This iterative relaxation method is an extension of Jain's iterative rounding method. We will start this talk with Jain's method and the necessary background.

Joint work with T. Kiraly, J. Naor, M. Salavatipour, R. Ravi, and M. Singh.