2
$\begingroup$

I am confused on a technicality on how Online Set Cover is defined.

One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be covered. Each time an element arrives, it reveals which sets contain it, and the algorithm must pick one of them into the solution if the element is not already covered.

Another way one could define it is: We are given upfront both a ground set $U$ and a collection $\mathcal{S}$ of subsets of $U$. In each time step we get a "request", which is an element of $U$ which needs to be covered. Again, we must serve the request by picking some set containing the element into our solution, unless the element is already covered.

Notice that in the latter definition, I am not saying that all elements of $U$ will eventually request to be covered.

These two formulations of Online Set Cover seem to be significantly different. In the latter setting we have more information about what a set might potentially help to cover. Also in the latter case, if the last element of $U$ makes a request then we automatically know that this is the last request, unlike in the first setting.

Online Set Cover seems to be most commonly defined as the first way. But in the paper "Tight Bounds for Online Weighted Tree Augmentation", since the tree is given upfront, it seems to fall in the latter setting. This is confusing because no distinction seems to be made that I can find between these two formulations. Is this because they are actually equivalent somehow in terms of complexity? Or are these genuinely two different problems, that are both interesting models?

Thanks for the help

$\endgroup$
5
  • $\begingroup$ Is it possible that each of these is reducible to the other, in the sense that given any c-competitive online algorithm A for one, one can always convert it into a c-competitive online algorithm A' for the other? $\endgroup$
    – Neal Young
    Mar 2, 2023 at 19:16
  • 1
    $\begingroup$ I'm confused about the first definition. Does the online algorithm know the sets upfront ("we are given $\cal S$ upfront") or not ("Each time an element arrives, it reveals all the sets which contain it.")? Also, when a set that contains an element is revealed, are all elements in the set specified, or just those elements that have been revealed so far? $\endgroup$
    – Neal Young
    Mar 5, 2023 at 21:05
  • $\begingroup$ @NealYoung In the first definition, we are given identifiers for a collection of sets upfront, but we don't know which elements they contain. When an element e arrives to be covered, it reveals which sets contain it (in the sense that we now know that those sets contain e). I see how my wording was a bit confusing there. Hope this clarifies things! $\endgroup$ Mar 8, 2023 at 6:23
  • $\begingroup$ Also, maybe I should mention that my current view is that these are simply different problems. $\endgroup$ Mar 8, 2023 at 6:24
  • $\begingroup$ What kinds of competitive ratios are you looking for (e.g. as a function of which parameters of the problem?), and are you interested in deterministic or randomized algorithms, or both? Can you summarize the results (upper and lower bounds on competitive ratios) that you know for each problem? $\endgroup$
    – Neal Young
    Mar 8, 2023 at 16:48

0

Your Answer

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