A Dynamic Algorithm for Weighted Submodular Cover Problem

Kiarash Banihashem, Samira Goudarzi, Mohammadtaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:2808-2830, 2024.

Abstract

We initiate the study of the submodular cover problem in a dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, we are given a monotone submodular function f:2V→R≥0 and the goal is to obtain a set S⊆V that minimizes the cost subject to the constraint f(S)=f(V). This is a classical problem in computer science and generalizes the Set Cover problem, 2-Set Cover, and dominating set problem among others. We consider this problem in a dynamic setting where there are updates to our set V, in the form of insertions and deletions of elements from a ground set V, and the goal is to maintain an approximately optimal solution with low query complexity per update. For this problem, we propose a randomized algorithm that, in expectation, obtains a (1−O(ϵ),O(ϵ−1))-bicriteria approximation using polylogarithmic query complexity per update.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-banihashem24a, title = {A Dynamic Algorithm for Weighted Submodular Cover Problem}, author = {Banihashem, Kiarash and Goudarzi, Samira and Hajiaghayi, Mohammadtaghi and Jabbarzade, Peyman and Monemizadeh, Morteza}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {2808--2830}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/banihashem24a/banihashem24a.pdf}, url = {https://proceedings.mlr.press/v235/banihashem24a.html}, abstract = {We initiate the study of the submodular cover problem in a dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, we are given a monotone submodular function $f : 2^{V} \to \mathbb{R}^{\ge 0}$ and the goal is to obtain a set $S \subseteq V$ that minimizes the cost subject to the constraint $f(S) = f(V)$. This is a classical problem in computer science and generalizes the Set Cover problem, 2-Set Cover, and dominating set problem among others. We consider this problem in a dynamic setting where there are updates to our set $V$, in the form of insertions and deletions of elements from a ground set $\mathcal{V}$, and the goal is to maintain an approximately optimal solution with low query complexity per update. For this problem, we propose a randomized algorithm that, in expectation, obtains a $(1-O(\epsilon), O(\epsilon^{-1}))$-bicriteria approximation using polylogarithmic query complexity per update.} }
Endnote
%0 Conference Paper %T A Dynamic Algorithm for Weighted Submodular Cover Problem %A Kiarash Banihashem %A Samira Goudarzi %A Mohammadtaghi Hajiaghayi %A Peyman Jabbarzade %A Morteza Monemizadeh %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-banihashem24a %I PMLR %P 2808--2830 %U https://proceedings.mlr.press/v235/banihashem24a.html %V 235 %X We initiate the study of the submodular cover problem in a dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, we are given a monotone submodular function $f : 2^{V} \to \mathbb{R}^{\ge 0}$ and the goal is to obtain a set $S \subseteq V$ that minimizes the cost subject to the constraint $f(S) = f(V)$. This is a classical problem in computer science and generalizes the Set Cover problem, 2-Set Cover, and dominating set problem among others. We consider this problem in a dynamic setting where there are updates to our set $V$, in the form of insertions and deletions of elements from a ground set $\mathcal{V}$, and the goal is to maintain an approximately optimal solution with low query complexity per update. For this problem, we propose a randomized algorithm that, in expectation, obtains a $(1-O(\epsilon), O(\epsilon^{-1}))$-bicriteria approximation using polylogarithmic query complexity per update.
APA
Banihashem, K., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P. & Monemizadeh, M.. (2024). A Dynamic Algorithm for Weighted Submodular Cover Problem. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:2808-2830 Available from https://proceedings.mlr.press/v235/banihashem24a.html.

Related Material