Lap Chi Lau
of Computer Science & Engineering
Chinese University of Hong Kong
Sept 11, 2008 (Thursday)
4:30p.m. - 5:30 p.m.
Rm. 833, Ho Sin Hang Engineering Building, CUHK
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.