Alberto
Caprara
Title:
A new approximation framework for set covering, with
applications in multidimensional packing
Abstract:
We introduce a new general framework for set covering, based on
the
combination of randomized rounding of the (near-)optimal solution of
the LP relaxation, leading to a
partial integer solution, and the
application of a "well-behaved" approximation algorithm to complete
this solution. If the value of the solution returned by the latter can
be appropriately bounded by feasible solutions of the LP dual, as is
the case for the most relevant generalizations of bin packing, the
method leads to improved approximation guarantees, along with a proof
of tighter integrality gaps for the LP relaxation.