Linear Programming Relaxation - Approximation and Integrality Gap

Approximation and Integrality Gap

Linear programming relaxation is a standard technique for designing approximation algorithms for hard optimization problems. In this application, an important concept is the integrality gap, the maximum ratio between the solution quality of the integer program and of its relaxation. Typically, this gap translates into the approximation ratio of an approximation algorithm.

For the set cover problem, Lovász proved that the integrality gap for an instance with n elements is H_n, the nth harmonic number. One can turn the linear programming relaxation for this problem into an approximate solution of the original unrelaxed set cover instance via the technique of randomized rounding (Raghavan & Tompson 1987). Given a fractional cover, in which each set S_i has weight w_i, choose randomly the value of each 0-1 indicator variable x_i to be 1 with probability w_i ×(ln n +1), and 0 otherwise. Then any element e_j has probability less than 1/(e×n) of remaining uncovered, so with constant probability all elements are covered. The cover generated by this technique has total size, with high probability, (1+o(1))(ln n)W, where W is the total weight of the fractional solution. Thus, this technique leads to a randomized approximation algorithm that finds a set cover within a logarithmic factor of the optimum. As Young (1995) showed, both the random part of this algorithm and the need to construct an explicit solution to the linear programming relaxation may be eliminated using the method of conditional probabilities, leading to a deterministic greedy algorithm for set cover, known already to Lovász, that repeatedly selects the set that covers the largest possible number of remaining uncovered elements. This greedy algorithm approximates the set cover to within the same H_n factor that Lovász proved as the integrality gap for set cover. There are strong complexity-theoretic reasons for believing that no polynomial time approximation algorithm can achieve a significantly better approximation ratio (Feige 1998).

Similar randomized rounding techniques, and derandomized approximation algorithms, may be used in conjunction with linear programming relaxation to develop approximation algorithms for many other problems, as described by Raghavan, Tompson, and Young.