# Fractional Set Cover

Here we derive a Lagrangian-relaxation algorithm for fractional set cover. The derivation illustrates the use of random stopping times to handle weights in the cost function.

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

We use -multicovers with as a stepping stone for finding fractional set covers. We apply the method of conditional probabilities to a randomized-rounding scheme to derive the following algorithm to find an approximately minimum-cost integer -multicover. Then we’ll use that algorithm, and scaling, to compute an approximately minimum-cost fractional set cover.

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

Let be the number of elements.

Theorem (performance guarantee).

Assume is an integer. For any such that , the algorithm returns an integer cover of coverage whose cost is at most , where is any minimum-cost cover with coverage .

We prove the theorem by applying the method of conditional probabilities to the following rounding scheme.

Fix any fractional cover with coverage .

Initialize for all .
Randomly sample sets independently from the distribution ;
with each sample , increment .
When achieves coverage , stop and return .

To analyze the rounding scheme, we use the following variant of the Chernoff bound. Suppose a random process starts in some fixed start state , then goes through a random sequence of states . As it goes, it maintains values (each initially zero). In state , each of the values is determined. (In our setting, the state consists of the first samples. Value represents the coverage of element by those samples.)

Lemma (Chernoff variant).

Let be a stopping time for the system. Fix , and . Assume that, at each time step, each of the counters increases by at most 1 and by at least in expectation. Then the expectation of the minimum of the values at time is at least .

(Note: there is a tighter version of this lemma.)

Now we analyze the rounding scheme.

Lemma (rounding scheme).

Assume is an integer. Fix any such that . Let be any fractional cover with coverage at least . Given , the rounding scheme returns an integer cover with coverage at least and whose expected cost is at most .

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

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

## Running time

The number of iterations for this algorithm can be large, even when is small. (Consider an example with and , and with two sets and , where equals and is arbitrarily large. The algorithm will choose set about times before choosing .)

As discussed in other notes here, it is possible to modify the algorithm to guarantee a polynomial running time.