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.

New contributor
Frizzylicious is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
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?

| cite | improve this answer | |
$\endgroup$
  • $\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 Jun 28 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 Jun 28 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 Jun 29 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 Jun 29 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 Jun 29 at 0:48

Your Answer

Frizzylicious is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.