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.

More… “Reduction to Set Cover”

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]