  We consider set covering problems where the underlying set system satisfies a
particular replacement property w.r.t. a given partial order on the elements:
Whenever a set is in the set system then a set stemming from it via the
replacement of an element by a smaller element is also in the set system. Many
variants of BIN PACKING that have appeared in the literature are such set
covering problems with ordered replacement. We provide a rigorous account on
the additive and multiplicative integrality gap and approximability of set
covering with replacement. In particular we provide a polylogarithmic upper
bound on the additive integrality gap that also yields a polynomial time
additive approximation algorithm if the linear programming relaxation can be
efficiently solved. We furthermore present an extensive list of covering
problems that fall into our framework and consequently have polylogarithmic
additive gaps as well.
