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