Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps

Details Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps

2010-12-15

arxiv.org/abs/1012.3295v1

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-13760