1
$\begingroup$

Here is a note about online set cover problem: we are initially given the $m$ sets, but we do not know which elements they contain. At any time $t$, we get a new element $e_t$ and learn which sets contain $e_t$. We then have to irrevocably pick a set that will cover $e_t$ if it is not already covered. The goal is again to minimize the number of sets we pick.

However, I'd like to think about another version: we have a group of sets $\mathcal{S} = \{ S_1, S_2, \cdots, S_m \} $ and a universal set $U=\{ e_1, \cdots, e_n \}$. $U$ can be covered by $\mathcal{S}$. But we don't know what elments each $S_i \in \mathcal{S}$ contains. Then $S_1$ comes and now we know what elements $S_1$ contains. Meanwhile, we have decide either you will use $S_1$ to cover $U$ or you discard it. Then, $S_2$ comes, you know what elements $S_2$ contains and decide to keep $S_2$ or discard it. The process is repeated until the sets you keep can cover $U$.

I want to ask if there is an algorithm works in the way I mentioned. Must we check all the $S_i \in \mathcal{S}$ in order to get a solution of set cover? Or what is the expected number of sets that have to be checked in order to get a solution of set cover? If we can also design a $O(\log n\log m)$ approximation ratio algorithm for this online version.

Improve this question
$\endgroup$
5
  • $\begingroup$ I don't understand your question. Can you state it more formally? $\endgroup$
    – Yuval Filmus
    Nov 25, 2015 at 16:21
  • $\begingroup$ I don't understand your "bad thing" / "good thing" sentences, or your question at the end. Can you edit to explain those more clearly? The question can be re-opened if it is edited to make clear what you are asking. $\endgroup$
    – D.W. ♦
    Nov 25, 2015 at 17:26
  • $\begingroup$ Thanks. Well, what properties do you want the algorithm to have? The obvious problem is the one that was in your question, but has since been edited out: "we might not be able to cover the universal set at the end, because we made a bad decision earlier that we cannot recover from" (you were entirely right about that). Does that answer your question? If so, we can write that in an answer. If that doesn't answer your question, can you think of any way to clarify what your question is and what requirements you want the algorithm to satisfy? $\endgroup$
    – D.W. ♦
    Nov 25, 2015 at 19:03
  • 1
    $\begingroup$ A simple adversary argument shows that you must take every set that you see unless it's entirely covered by sets that you already took, and the resulting approximation ratio is $m$. $\endgroup$
    – Yuval Filmus
    Nov 25, 2015 at 19:05
  • $\begingroup$ If that's the question, you should edit the question to state that. Don't leave clarifications down in the comment thread: we want you to edit your question to improve it and add all relevant information, so that people don't need to read the comment thread. And you should edit the question to reflect the feedback you've gotten. Does Yuval's comment answer your question? It seems it does. If so, ask him to post it as an answer. $\endgroup$
    – D.W. ♦
    Nov 26, 2015 at 7:49

1 Answer 1

Reset to default
1
$\begingroup$

A simple adversary argument shows that you must take every set you are offered, unless it's entirely covered by elements already taken. Indeed, otherwise there must be some element $x$ which hasn't appeared before; perhaps it will never appear again, so you must take the set.

Consider now the following instance: $$ \{x_1\},\{x_2,\},\ldots,\{x_{m-1}\},\{x_1,\ldots,x_m\}. $$ The algorithm takes all $m$ sets, but the last one would have sufficed. This shows that the approximation ratio can be as bad as $m$, the number of sets.

Improve this answer
$\endgroup$

Your Answer

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

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