A Dynamic Algorithm for Weighted Submodular Cover Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929419946295296 |
|---|---|
| author | Banihashem, Kiarash Goudarzi, Samira Hajiaghayi, MohammadTaghi Jabbarzade, Peyman Monemizadeh, Morteza |
| author_facet | Banihashem, Kiarash Goudarzi, Samira Hajiaghayi, MohammadTaghi Jabbarzade, Peyman Monemizadeh, Morteza |
| contents | We initiate the study of the submodular cover problem in 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(ε), O(ε^{-1}))$-bicriteria approximation using polylogarithmic query complexity per update. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10003 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Dynamic Algorithm for Weighted Submodular Cover Problem Banihashem, Kiarash Goudarzi, Samira Hajiaghayi, MohammadTaghi Jabbarzade, Peyman Monemizadeh, Morteza Data Structures and Algorithms Machine Learning We initiate the study of the submodular cover problem in 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(ε), O(ε^{-1}))$-bicriteria approximation using polylogarithmic query complexity per update. |
| title | A Dynamic Algorithm for Weighted Submodular Cover Problem |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2407.10003 |