Iterative Methods in Combinatorial Optimization (Invited Talk)

R. Ravi
In these lectures, I will describe a simple iterative method that supplies new proofs of integrality of linear characterizations of various basic problems in combinatorial optimization, and also allows adaptations to design approximation algorithms for NP-hard variants of these problems involving extra "degree-like" budget constraints. It is inspired by Jain's iterative rounding method for designing approximation algorithms for survivable network design problems, and augmented with a relaxation idea in the work of Lau, Naor, Salvatipour...