# 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.