# What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

Let $$X$$ be the universe of elements, $$F$$ a collection of subsets $$S \subseteq X$$, each with an associated cost. The goal is to find a subcollection $$C \subseteq F$$ of minimum total cost which covers $$X$$.

GreedySetCover(X,F)
1 C ← ∅
2 U ← X
3 while U ≠ ∅
4     Find set S ∈ F \ C that minimizes α = cost(S) / |S ∩ U|
5     C ← C ∪ {S}
6     U ← U \ S
7 end while
8 return C


Let $$N = |U|$$ and $$M = |F|$$. Then, in the worst-case, all subsets $$S \subseteq X$$ have to be searched. In the first iteration we search $$M$$ sets, in the second iteration we search $$M - 1$$ sets and so on. The cost of computing $$|S \cap U|$$ is $$O(N)$$.

$$T(n) = N (M + (M - 1) + (M - 2) + \cdots + 2 + 1) = N M(M+1)/2 = O(N M^2)$$

I think this is correct. I am not sure how to approach the average case time complexity however.

Let $$n$$ be the total number of elements in all sets in $$F$$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time you cover an element, update the cost of all sets that cover it. Then there are n total updates, so the total time for the algorithm using a priority queue in this way is $$O(n \log n)$$.
• [shameless self-promotion] Let $\ell=\max_e \min_{S\ni e} w(S)$. Then $\ell\le OPT \le n\ell$. Round each weight to its nearest multiple of $\ell/n^2$. This changes the cost of any cover by at most an additive $\ell/n \le OPT/n$, and now the weights are a subset of the first $n^3$ integer multiples of $\ell/n^2$. So, using an approximate data structure instead of a standard priority queue, the algorithm takes linear time, while the approximation ratio degrades by (only) a $1+1/\text{polylog} (n)$ factor. – Neal Young Jun 28 at 14:11
• Hmm, and I overlooked that the priorities are of the form $w(S)/k$ for a set $S$ and integer $k\le |S|$. But I don't see what you have in mind about presorting and using buckets.. aren't there too many (more than $O(n)$ many) possible priorities? – Neal Young Jun 29 at 0:11
• Each set $S_i$ has $|S_i|$ possible priorities, one for each of the possible choices of $k$ up to its actual input cardinality. So the total number of possible priorities is $n=\sum|S_i|$. Round those numbers, sort them, and use the ranks in their sorted order as priorities in a bucket queue. – David Eppstein Jun 29 at 0:48
• Oh, of course, very nice. I was thinking of $n$ as the number of elements, but working with the sum of the set sizes is the right thing to do. And your suggestion gives linear time (using, say, radix sort) while degrading the approximation ratio by at most a $1+1/n$ factor. – Neal Young Jun 29 at 0:48