Iterative Relaxation

By

Professor Lap Chi Lau
Department of Computer Science & Engineering
The Chinese University of Hong Kong
 
 

Date: Sept 11, 2008 (Thursday)

Time: 4:30p.m. - 5:30 p.m.

Venue: Rm. 833, Ho Sin Hang Engineering Building, CUHK

 

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.