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:
- $ C \leftarrow \varnothing$
- 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.$
- 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$ .
