World's most popular travel blog for travel bloggers.

# [Answers] Another version of the online set cover problem?

, ,
Problem Detail:

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.

#### Answered By : Yuval Filmus

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.

Question Source : http://cs.stackexchange.com/questions/49963

3.2K people like this