## 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