Unconstrained Set Multicover

Several entries on unconstrained Set Multicover.

 



Entries on unconstrained Set Multicover

Reduction to Set Cover

Unconstrained Set Multicover reduces to Set Cover.
Unconstrained Set Multicover has an approximation-preserving reduction to Set Cover that also preserves maximum set size. This reduction (and previous results on Set Cover) imply that a localized rounding scheme and a greedy algorithm both give {\rm H}(\max _ s |s|)-approximation.

A greedy algorithm for unconstrained Set Multicover

{\rm H}(n)-approximation for unconstrained Set Multicover by oblivious randomized rounding.
This example illustrates the use of “Wald’s equation for dependent decrements”. The rounding scheme and algorithm can be exponentially slow. In a later example, we speed it up using non-uniform increments.

Non-uniform increments

Applying non-uniform increments to unconstrained Set Multicover.
The algorithm in the previous note can be exponentially slow. Here we use non-uniform increments to give a faster rounding scheme and algorithm.

Questions for later

Generalize results here to constrained Set Multicover (where the solution must take each set s at most once). Aim for {\rm H}(\max _ s |s|)-approximation (matching Wolsey).

Related

  •  [1, Exercise 13.4.1]

MathJax is loading, equations are not yet displayed...