DIMACS TR: 94-53

Improved Approximations of Packing and Covering Problems



Author: Aravind Srinivasan

ABSTRACT

Several important NP-hard combinatorial optimization problems can be posed as packing/covering integer programs; the randomized rounding technique of Raghavan and Thompson is a powerful tool to approximate them well. We present one elementary unifying property of all these integer programs (IPs), and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This also yields a pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees significantly better than those known.

Let the packing/covering IP have, w.l.o.g., constraint matrix A being an element of [0,1]^{n x m}, r.h.s. vector b being an element of [1, infinity)^n with min_i b_i = B, and objective function vector c being an element of [0,1]^m; let y* be the optimum value of its standard linear programming (LP) relaxation. For packing, while known methods show a feasible integral solution of value t_1 = Omega(y*/ n^{1/B}), we get an Omega(t_1^{B/(B-1)}) bound. If A has entries in {0,1}, these are improved, respectively, to t_2 = Omega(y*/ n^{1/(B+1)}) and Omega(t_2^{(B + 1)/B}). For covering, we get an improved 1 + O(max {ln(nB/y*)/B, sqrt{ln(n/y*)/B}\}) approximation bound and for the key unweighted set cover problem, we tighten the constants to get a ln(n/y*) + o(ln(n/y*)) + O(1) approximation ratio. This is never more than a multiplicative (1 + o(1)) or an additive O(1) factor above the classical bound (ln d + O(1), where $d$ is the largest size of a set) and is usually much better; in the best case, our improvement is by a Theta(log n / log log n) factor in the approximation ratio. Other improvements are for B-domination problems on graphs, file-sharing in distributed networks, and related problems.

Paper only.


DIMACS Home Page