0
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

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 Neal Young in a comment is basically the same thing, just using a 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?

Improve this answer
$\endgroup$
5
  • $\begingroup$ [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. $\endgroup$
    – Neal Young
    Commented Jun 28, 2020 at 14:11
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Jun 28, 2020 at 20:07
  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Commented Jun 29, 2020 at 0:11
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Jun 29, 2020 at 0:48
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Jun 29, 2020 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.