Here we derive a Lagrangian-relaxation algorithm for unweighted fractional set cover.

Click for problem definition…

An instance is specified by a collection $S$ of subsets of a universe $U$ . A (fractional set) cover $x$ assigns a non-negative weight $x_ s$ to each set $s\in S$ . The size of the cover is $|x| = \sum _ s x_ s$ . Its coverage of element $e$ is $x(e) = \sum _{s\ni e} x_ e$ . Its minimum coverage is $\min _{e\in U} x(e)$ . The cover is feasible if its minimum coverage is at least 1. The goal is to find a minimum size feasible cover.

The cover is an integer cover if each $x_ s$ is an integer.

A fractional cover $x$ is a $C$ -multicover if its coverage of every element is at least $C$ .

We’ll first apply the method of conditional probabilities to a randomized-rounding scheme to derive the following algorithm to find an approximately minimum-size integer $C$ -multicover.

	input: Collection $S$ of subsets of $U$ , coverage $C$ , and $\varepsilon \in (0,1)$ .
	output: Integer cover $\tilde x$ of near-minimum size with minimum coverage at least $C$ .
1.	Initialize $\tilde x_ s=0$ for every set $s\in S$ . Recall that $\tilde x(e)$ denotes $\sum _{s\ni e} \tilde x_ s$ .
2.	While the minimum coverage is less than $C$ :
3.	Choose a set $s\in S$ maximizing $\sum _{e\ni s} (1-\varepsilon )^{\tilde x(e)}$ .
4.	Increase $\tilde x_ s$ by 1.
5.	Return $\tilde x$ .

Let $n=|U|$ be the number of elements.

Theorem (performance guarantee).

For any $\varepsilon \in (0,1)$ , assuming $C \ge 2\ln (n)/(1-\varepsilon )\varepsilon ^2$ , the algorithm returns an integer cover $\tilde x$ of minimum coverage $C$ whose size $|\tilde x|$ is at most $\lceil |x^*|/(1-\varepsilon )\rceil$ , where $x^*$ is any minimum-size cover with minimum coverage $C$ .

The algorithm and the derivation are essentially from [1].

Deriving the algorithm

We derive the algorithm by applying the method of conditional probabilities to the following rounding scheme. Fix any fractional cover $x$ with minimum coverage $C$ .

Fix $N=\lceil |x|/(1-\varepsilon ) \rceil$ .
Randomly sample $N$ sets independently from the distribution $x/|x|$ .
Return the integer cover $\tilde x$ such that, for each set $s\in S$ , the weight $\tilde x_ s$ of $s$ equals the number of times $s$ was sampled.

Lemma.

Let $x$ be any fractional cover with minimum coverage at least $C$ . For any $\varepsilon \in (0,1)$ such that $C\ge 2(1-\varepsilon )\ln (m)\varepsilon ^2$ , given $x$ , with positive probability, the rounding scheme returns an integer cover $\tilde x$ of size $N=\lceil |x|/(1-\varepsilon ) \rceil$ whose minimum coverage is at least $C$ .

Click for proof…

The size of the cover $\tilde x$ is inevitably $N$ , because each of the $N$ samples increases the size by 1. Next we bound the coverage.

Fix any element $e\in U$ . With each of the $N$ samples, the probability that the sampled set contains $e$ is $\sum _{s\ni e} x_ s /|x|$ , which, since $x$ has minimum coverage $C$ , is at least $C/|x|$ . Thus, the expectation of $\tilde x(s)$ is at least $N\cdot C/|x| \ge C/(1-\varepsilon )$ .

Consider $\tilde x(s)$ as the sum $\sum _{t=1}^ N [e \in s_ t]$ of $N$ independent random indicator variables (the $t$ th of which is 1 the $t$ th sampled set $s_ t$ contains $e$ , and zero otherwise). By the Chernoff bound, the probability that $\tilde x(e)$ is less than $C=(1-\varepsilon ) C/(1-\varepsilon )$ is less than

\[ \exp (-\varepsilon ^2 (C/(1-\varepsilon ))/2) ~ \le ~ 1/n. \]

(The inequality follows from the assumption on $C$ .)

Thus, the expected number of elements $e$ with $\tilde x(e) \lt C$ is less than 1. So, with positive probability, $\tilde x$ has minimum coverage at least $C$ .

Next, to prove the theorem, we describe how applying the method of conditional probabilities to the rounding scheme gives the algorithm.

Click for proof of theorem…

Say that an element $e$ is “undercovered” (when the rounding scheme finishes) if $\tilde x(e) \lt C$ . The algorithm will emulate the rounding scheme, but instead of choosing each set $s$ randomly, it will choose each set so as to keep the conditional expectation of the number of undercovered elements below 1.

Recall that $s_ t$ is the $t$ th sampled set. In using the Chernoff bound for each element, the analysis of the rounding scheme implicitly bounds the number of undercovered elements by

\[ \Phi ~ =~ \sum _{e\in U} \frac{(1-\varepsilon )^{\tilde x(e)} }{ (1-\varepsilon )^{(1-\varepsilon )C/(1-\varepsilon ) } } ~ =~ \sum _{e\in U} \frac{ \prod _{t=1}^ N (1-\varepsilon [e \in s_ t])}{ (1-\varepsilon )^{ C } }, \]

then shows the expectation of $\Phi$ is at most 1.

(To understand where $\Phi$ comes from requires a good understanding of the proof of the Chernoff bound. Here are the essentials. For each undercovered element $e$ , the term for $e$ in the sum is at least 1, so the number of undercovered elements is at most $\Phi$ . The proof of the Chernoff bound shows that the expectation of the term for each $e$ in $\Phi$ is less than $\exp (-\varepsilon ^2 (C/(1-\varepsilon ))/ 2)$ . By the assumption on $C$ in the analysis of the rounding scheme, this is at most $1/n$ , so the expectation of $\Phi$ is less than 1.)

Since $\Phi$ is an upper bound on the number of undercovered elements, to keep the conditional expectation of the number of undercovered elements below 1, it suffices to keep the conditional expectation of $\Phi$ below 1. This is what the algorithm will do.

Fix any $t\in \{ 0,1,\ldots ,N\}$ . Recall that, for any element $e$ , $\Pr [e\in s_ t] \ge C/|x|$ . One pessimistic estimator for the conditional expectation of $\Phi$ , given the first $t$ elements, is

\begin{equation} \label{eq:1} \phi _ t ~ =~ \sum _{e\in U} \frac{ \prod _{r=1}^ t (1-\varepsilon [e\in s_ t]) \times \prod _{r=t+1}^ N (1-\varepsilon C/|x|) }{ (1-\varepsilon )^{ C } }. \end{equation}

To reach a successful outcome, it suffices for the algorithm to choose each element to ensure that $\phi _ t$ does not increase, so that $\Phi = \phi _ N \le \phi _{N-1} \le \cdots \le \phi _0 \lt 1$ . How can it choose $e_{t+1}$ to ensure $\phi _{t+1} \le \phi _ t$ ? Letting $\omega ^ s_ t$ denote the term for $s$ in $\phi _ t$ (so $\phi _ t = \sum _ s \omega ^ s_ t$ ) if the algorithm takes some set $s$ to be $s_{t+1}$ , then

\[ \phi _{t+1} ~ =~ \sum _{e\in U} \frac{ 1-\varepsilon [e\in s] }{ 1-\varepsilon C/|x|} \omega ^ s_ t. \]

If $s$ were chosen randomly as in the sampling scheme, then (for any element $e$ ), $\Pr [e\in s] \ge C/|x|$ , so (by inspection above) the expectation of $\phi _{t+1}$ would be at most $\phi _ t$ .

So, to ensure $\phi _{t+1}\le \phi _ t$ , it suffices to choose $s$ to minimize $\phi _{t+1}$ . Inspecting (\ref{eq:1}), the second product in the numerator, and the denominator, can be ignored (not only are they the same for all elements $e$ , they are also independent of all choices so far). By calculation (factoring the irrelevant terms out and simplifying), choosing set $s$ minimizes $\phi ’_{t+1}$ if and only if it maximizes

\[ \sum _{e\ni s} (1-\varepsilon )^{\textstyle \tilde x(e)}, \]

where $\tilde x$ denotes the cover at the start of the iteration. Thus, the algorithm at the top chooses each element to minimize the pessimistic estimator. This keeps the pessimistic estimator from increasing, ensuring a successful outcome.

Finally, note that to do this, the algorithm does not need to know $x$ , yet is guaranteed to do as well as the rounding scheme for any $x$ . This proves the theorem.

Finding a near-optimal fractional set cover

Given a collection of sets $S$ , and an arbitrary $\varepsilon \in (0,1)$ , one can also use the algorithm to compute a $(1+O(\varepsilon ))$ -approximate fractional (non-integer) set cover for the given instance as follows.

Define coverage $C$ to be $C = 2(1-\varepsilon )\ln (m)/\varepsilon ^2$ . Run the algorithm with coverage $C$ to find a $(1/(1-\varepsilon ))$ -approximate integer $C$ -multicover $\tilde x$ , then scale it by $1/C$ to obtain the fractional set cover $x=\tilde x/C$ for the original problem, with minimum coverage 1. The cover $x$ will have size at most $1+\varepsilon +o(\varepsilon ^2)$ times the minimum size of any fractional set cover (with minimum coverage 1).

The number of iterations will be $O(n \log (n)/\varepsilon ^2)$ , because each iteration increases the size of $\tilde x$ by 1, and the size of $\tilde x$ is at most $n C$ .

Running time

The algorithm will take about $|x^*|$ iterations, where $x^*$ is the minimum-size fractional cover of minimum coverage $C$ . This is bounded by $n C$ , which can be exponential if $C$ is large.

If the coverage $C$ is large (say, $C \ge 4\ln (m)/\varepsilon ^2$ ), scaling the coverage can ensure polynomial running time. Replace $C$ by $C’ = C/\alpha$ , where integer $\alpha = \lceil C \varepsilon ^2 / 2(1-\varepsilon )\ln (m) \rceil$ is chosen maximally such that $C’ \ge 2(1-\varepsilon )\ln (m)/\varepsilon ^2$ . Run the algorithm with coverage $C’$ to find a $(1/(1-\varepsilon ))$ -approximate integer cover $\tilde x$ with respect to $C’$ , then scale $\tilde x$ up by $\alpha$ to obtain the integer cover $x=\alpha \tilde x$ for the original problem.

The cover $x$ will have minimum coverage at least $C$ , and size at most $1+\varepsilon + o(\varepsilon ^2)$ times the minimum size of any fractional cover with minimum coverage $C$ .

The number of iterations will be at most $n C’ = O(n\log (n)/\varepsilon ^2)$ .

Background

Bibliography

[1]	N. E. Young. Randomized rounding without solving the linear program. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 170–178, San Francisco, California, 22–24 Jan. 1995.

Notes on algorithms

Lecture notes on algorithms

Fractional Set Cover / unweighted

Deriving the algorithm

Finding a near-optimal fractional set cover

Running time

Related

Background

Bibliography