<p>Let <span class="math-container">$n$</span> be the total number of elements in all sets in <span class="math-container">$F$</span>, 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 <span class="math-container">$O(n \log n)$</span>.</p>
<p>The linear time algorithm for the unweighted case mentioned by Neal Young in a comment is basically the same thing, just using a <a href="https://en.wikipedia.org/wiki/Bucket_queue" rel="nofollow noreferrer">bucket queue</a> as the priority queue instead of a comparison-based priority queue.</p>
<p>As for average case, you haven't provided enough information to answer that. Average over what input distribution?</p>

CC BY-SA 4.0
2020-06-28T14:11:59.573Z
[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](https://scholar.google.com/scholar?cluster=10194749687892272148&hl=en&as_sdt=1,22) 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
CC BY-SA 4.0
2020-06-28T20:07:44.713Z
Approximate data structure seems like overkill when you can presort all possible rounded priorities and then use a bucket queue prioritized by position in the sorted order.
David Eppstein
CC BY-SA 4.0
2020-06-29T00:11:32.203Z
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
CC BY-SA 4.0
2020-06-29T00:48:03.840Z
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
CC BY-SA 4.0
2020-06-29T00:48:34.177Z
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
CC BY-SA 4.0
2020-06-26T18:10:11.917Z
2020-06-27T20:45:54.890Z
2020-06-27T20:45:54.890Z
David Eppstein
<p>Let <span class="math-container">$X$</span> be the universe of elements, <span class="math-container">$F$</span> a collection of subsets <span class="math-container">$S \subseteq X$</span>, each with an associated cost. The goal is to find a subcollection <span class="math-container">$C \subseteq F$</span> of minimum total cost which covers <span class="math-container">$X$</span>.</p>
<pre><code>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
</code></pre>
<p>Let <span class="math-container">$N = |U|$</span> and <span class="math-container">$M = |F|$</span>. Then, in the worst-case, all subsets <span class="math-container">$S \subseteq X$</span> have to be searched. In the first iteration we search <span class="math-container">$M$</span> sets, in the second iteration we search <span class="math-container">$M - 1$</span> sets and so on. The cost of computing <span class="math-container">$|S \cap U|$</span> is <span class="math-container">$O(N)$</span>.</p>
<p><span class="math-container">$$T(n) = N (M + (M - 1) + (M - 2) + \cdots + 2 + 1) = N M(M+1)/2 = O(N M^2)$$</span></p>
<p>I think this is correct. I am not sure how to approach the average case time complexity however.</p>

CC BY-SA 4.0
2020-06-26T19:44:22.360Z
The unweighted special case has a [linear-time algorithm](https://cs.stackexchange.com/questions/16142/how-to-implement-greedy-set-cover-in-a-way-that-it-runs-in-linear-time).
Neal Young
<approximation-algorithms><set-cover><average-case-complexity><analysis-of-algorithms><complexity-theory>
What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?
Frizzylicious
# What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

(Asked by: username_0 on 2020-06-26)

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.

**Tags:** approximation-algorithms, set-cover, average-case-complexity, analysis-of-algorithms, complexity-theory

> **Comments:**
> **username_1**: The unweighted special case has a [linear-time algorithm](https://cs.stackexchange.com/questions/16142/how-to-implement-greedy-set-cover-in-a-way-that-it-runs-in-linear-time).  

---

## 1 answers

### Answer by username_2 on 2020-06-26. Score: 2

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)$.

The linear time algorithm for the unweighted case mentioned by username_1 in a comment is basically the same thing, just using a [bucket queue](https://en.wikipedia.org/wiki/Bucket_queue) as the priority queue instead of a comparison-based priority queue.

As for average case, you haven't provided enough information to answer that. Average over what input distribution?

> **Comments:**
> **username_1**: [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](https://scholar.google.com/scholar?cluster=10194749687892272148&hl=en&as_sdt=1,22) 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.  
> **username_2**: Approximate data structure seems like overkill when you can presort all possible rounded priorities and then use a bucket queue prioritized by position in the sorted order.  
> **username_1**: 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?  
> **username_2**: 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.  
> **username_1**: 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.  

---

