# Fractional Set Cover / unweighted

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

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

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

 input: Collection of subsets of , coverage , and . output: Integer cover of near-minimum size with minimum coverage at least . 1. Initialize for every set . Recall that denotes . 2. While the minimum coverage is less than : 3. Choose a set maximizing . 4. Increase by 1. 5. Return .

Let be the number of elements.

Theorem (performance guarantee).

For any , assuming , the algorithm returns an integer cover of minimum coverage whose size is at most , where is any minimum-size cover with minimum coverage .

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 with minimum coverage .

Fix .
Randomly sample sets independently from the distribution .
Return the integer cover such that, for each set , the weight of equals the number of times was sampled.

Lemma.

Let be any fractional cover with minimum coverage at least . For any such that , given , with positive probability, the rounding scheme returns an integer cover of size whose minimum coverage is at least .

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 , and an arbitrary , one can also use the algorithm to compute a -approximate fractional (non-integer) set cover for the given instance as follows.

Define coverage to be . Run the algorithm with coverage to find a -approximate integer -multicover , then scale it by to obtain the fractional set cover for the original problem, with minimum coverage 1. The cover will have size at most times the minimum size of any fractional set cover (with minimum coverage 1).

The number of iterations will be , because each iteration increases the size of by 1, and the size of is at most .

## Running time

The algorithm will take about iterations, where is the minimum-size fractional cover of minimum coverage . This is bounded by , which can be exponential if is large.

If the coverage is large (say, ), scaling the coverage can ensure polynomial running time. Replace by , where integer is chosen maximally such that . Run the algorithm with coverage to find a -approximate integer cover with respect to , then scale up by to obtain the integer cover for the original problem.

The cover will have minimum coverage at least , and size at most times the minimum size of any fractional cover with minimum coverage .

The number of iterations will be at most .