Iterative Relaxation Methods in Combinatorial Optimization and Approximation Algorithms
(L. C. Lau)

Linear programming has been a successful tool in combinatorial optimization and the design of approximation algorithms. In this project, we plan to develop the iterative relaxation method as a unifying method to analyse linear programming formulations to design both exact algorithms and approximation algorithms, and to use this understanding to obtain substantial new results in both areas.

The iterative relaxation method was introduced by Jain (known as the iterative rounding method) to design a 2-approximation algorithm for the survivable network design problem. Recently, we have successfully applied the iterative relaxation method to degree bounded network design problems. Using this method, we obtained the first constant factor approximation algorithms for many degree-constrained network design problems, and also settled a long standing conjecture of Goemans affirmatively. These results show that the iterative relaxation method is much more powerful and versatile than thought before.

We have further extended this method to give new proofs of exact linear programming formulations for various classical combinatorial optimization problems. This understanding leads us to obtain new approximation results, and also improved and simpler approximation algorithms for various problems. We believe that the iterative relaxation method is a powerful and general method to design both exact algorithms and approximation algorithms, and also has much potential to lead to new breakthroughs. Currently, we are searching for new applications of this method. Also, we are trying to use this method to tackle the asymmetric travelling salesman problem (ATSP), a major open problem in approximation algorithms is whether there is a polynomial time constant factor approximation algorithm for ATSP.