"You're Fired!": Greedy Set Selection with Dismissals
The next talk in the ICE-TCS seminar series is given by Dror Rawitz, professor at Bar-Ilan University
The next talk in the ICE-TCS seminar series is given by Dror Rawitz, professor at Bar-Ilan University on Thursday 13th of October at 14:00 in room M109.
We study variants of Set Cover in a non-standard online setting. Subsets of a weighted ground set of elements arrive one by one, where each subset has a cost. Upon arrival of a subset, the algorithm must decide whether to accept it or to reject it, and it may also dismiss previously accepted subsets. Rejections and dismissals are irrevocable. We consider two variants of the problem, each one treating uncovered elements differently. In the Online Multiset Multicover problem each element has a demand, and the algorithm has to select a collection of subsets which minimizes the total cost of subsets taken plus the total weight of uncovered demands. We present an online algorithm that is based on a greedy rule and a matching lower bound on the competitive ratio of this problem.
In the Online Budgeted Maximum Coverage problem the algorithm has to select a collection of subsets whose total cost is at most a given budget, and the goal is to maximize the total weight of covered elements. We present matching lower and upper bounds on the competitive ratio of deterministic algorithms in terms of three parameters: the size of the universe, the maximum weight of a set, and the maximum ratio between the cost of a set and the budget. We also present a randomized O(1)-competitive algorithm. Our results also apply to Removable Online Knapsack which is the preemptive version of Online Knapsack.
