Online Multiset Submodular Cover

We study the Online Multiset Submodular Cover problem (OMSC), where we are given a universe U of elements and a collection of subsets S⊆2^U. Each element u_j∈U is associated with a nonnegative, nondecreasing, submodular polynomially computable set function f_j. Initially, the elements are uncovered, and therefore we pay a penalty per each unit of uncovered element. Subsets with various coverage and cost arrive online. Upon arrival of a new subset, the online algorithm must decide how many copies of the arriving subset to add to the solution. This decision is irrevocable, in the sense that the algorithm will not be able to add more copies of this subset in the future. On the other hand, the algorithm can drop copies of a subset, but such copies cannot be retrieved later. The goal is to minimize the total cost of subsets taken plus penalties for uncovered elements. We present an O(ρ_max)-competitive algorithm for OMSC that does not dismiss subset copies that were taken into the solution, but relies on prior knowledge of the value of ρ_max, where ρ_max is the maximum ratio, over all subsets, between the penalties covered by a subset and its cost. We provide an Olog(ρ_max)ρ_max-competitive algorithm for OMSC that does not rely on advance knowledge of ρ_max but uses dismissals of previously taken subsets. Finally, for the capacitated versions of the Online Multiset Multicover problem, we obtain an O(ρ_max^′)-competitive algorithm when ρ_max^′ is known and an Olog(ρ_max^′)ρ_max^′-competitive algorithm when ρ_max^′ is unknown, where ρ_max^′ is the maximum ratio over all subset incarnations between the penalties covered by this incarnation and its cost.