Several entries on unconstrained Set Multicover.

Click for background material…

Problem definition: Unconstrained Set Multicover. The problem is a generalization of Set Cover. An instance is specified by a weighted Set Cover instance, along with an integer demand $d_ e\gt 0$ for every element $e$ . A fractional multicover $x$ assigns a weight (multiplicity) $x_ s$ to each set $s$ such that, for every element $e$ , the total weight assigned to sets containing $e$ is at least $d_ e$ . If each multiplicity $x_ s$ is an integer, then $x$ is called just a multicover. The goal is to find a multicover of minimum cost, $c\cdot x = \sum _ s c_ s x_ s$ .

The name “Set Multicover” conventionally refers to the variant of the above problem with the added constraint that each set can be taken at most once ( $\forall s. x_ s\le 1$ ). Sometimes, this variant is called “constrained” Set Multicover [1, Ch.13].

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

[1, Exercise 13.4.1]

Bibliography

[1]	V. Vazirani. Approximation Algorithms. Springer Verlag, 2003.

Notes on algorithms

Lecture notes on algorithms

Unconstrained Set Multicover