# Is time complexity of the greedy set cover algorithm cubic?

I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $$M^2N$$, where $$M$$ denotes the number of sets, and $$N$$ the overall number of elements.

Question: true or false?

Approximation Algorithms, Vazirani, 2001, 1e, p.16, Algorithm 2.2:

1. $$C \leftarrow \varnothing$$
2. While $$C \neq U$$ do Find the set whose cost-effectiveness is smallest, say $$S$$.

Let $$\alpha = \frac{c(S)}{|S – C|}$$, i.e., the cost-effectiveness of $$S$$.

Pick $$S$$, and for each $$e \in S – C$$, set $$\text{price}(e) = \alpha$$.

$$C \leftarrow C \cup S.$$

1. Output the picked sets.

In the first iteration, the cost-effectiveness of $$M$$ sets have to be computed.

In the second iteration, the cost-effectiveness of $$M-1$$ sets have to be computed.

Since everything between $$1$$ and $$M$$ iterations may be needed to find the sets that cover all elements, in the mean it may be $$M/2$$ iterations.

I.e. in the worst case we need to compute $$M + (M-1) + (M-2) + … + 1 = M(M+1)/2$$ times the cost effectiveness.

Determining cost-effectiveness requires the computation of a difference which has time complexity proportional to the number of elements.

Hence, the time complexity is dominated by the term $$M^2N$$.

Posted on Categories proxies