Fractional Set Cover / unweighted

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

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.

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

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

MathJax is loading, equations are not yet displayed...