## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 2393-2411 |

Number of pages | 19 |

Journal | Algorithmica |

Volume | 86 |

Issue number | 7 |

DOIs | |

Publication status | Published - 8 May 2024 |

### Bibliographical note

Publisher Copyright:© The Author(s) 2024.

## Other keywords

- Capacitated covering
- Competitive analysis
- Online multiset multicover
- Submodular coverage
- Team formation