Unconstrained Set Multicover

Several 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 -approximation.

A greedy algorithm for unconstrained Set Multicover

-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 at most once). Aim for -approximation (matching Wolsey).

Related

•  [1, Exercise 13.4.1]