Edge Connectivity: Iterative rounding of a Linear Program
Tanmoy Chakraborty
University of Pennsylvania.
06-09-07

---

Abstract

It is believed that NP-hard problems do not have polynomial time algorithms, so people devise algorithms to find approximate solutions to such problems. Edge-connectivity is such a problem, and Kamal Jain gave a factor 2 approximation algorithm for it. The algorithm uses an IP (integer program) formulation of the problem, solves its LP relaxation and then rounds the fractional optimal solution obtained to get an integral solution that is within factor 2 of the optimum.

This has been the standard approach for many approximation algorithms. However, Jain formulated a new rounding scheme in this paper, and the technique, which was named iterative rounding, has been used in many other problems. In this presentation, I shall describe Jain's, what is considered the first, use of iterative rounding.