Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover

Victoria Crawford
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:9517-9537, 2023.

Abstract

In this paper, we consider the optimization problem Submodular Cover (SC), which is to find a minimum cost subset of a ground set $U$ such that the value of a submodular function $f$ is above a threshold $\tau$. In contrast to most existing work on SC, it is not assumed that $f$ is monotone. Two bicriteria approximation algorithms are presented for SC that, for input parameter $0 < \epsilon < 1$, give $O( 1 / \epsilon^2 )$ ratio to the optimal cost and ensures the function $f$ is at least $\tau(1 - \epsilon)/2$. A lower bound shows that under the value query model shows that no polynomial-time algorithm can ensure that $f$ is larger than $\tau/2$. Further, the algorithms presented are scalable to large data sets, processing the ground set in a stream. Similar algorithms developed for SC also work for the related optimization problem of Submodular Maximization (KCSM). Finally, the algorithms are demonstrated to be effective in experiments involving graph cut and data summarization functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-crawford23a, title = {Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover}, author = {Crawford, Victoria}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {9517--9537}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/crawford23a/crawford23a.pdf}, url = {https://proceedings.mlr.press/v206/crawford23a.html}, abstract = {In this paper, we consider the optimization problem Submodular Cover (SC), which is to find a minimum cost subset of a ground set $U$ such that the value of a submodular function $f$ is above a threshold $\tau$. In contrast to most existing work on SC, it is not assumed that $f$ is monotone. Two bicriteria approximation algorithms are presented for SC that, for input parameter $0 < \epsilon < 1$, give $O( 1 / \epsilon^2 )$ ratio to the optimal cost and ensures the function $f$ is at least $\tau(1 - \epsilon)/2$. A lower bound shows that under the value query model shows that no polynomial-time algorithm can ensure that $f$ is larger than $\tau/2$. Further, the algorithms presented are scalable to large data sets, processing the ground set in a stream. Similar algorithms developed for SC also work for the related optimization problem of Submodular Maximization (KCSM). Finally, the algorithms are demonstrated to be effective in experiments involving graph cut and data summarization functions.} }
Endnote
%0 Conference Paper %T Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover %A Victoria Crawford %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-crawford23a %I PMLR %P 9517--9537 %U https://proceedings.mlr.press/v206/crawford23a.html %V 206 %X In this paper, we consider the optimization problem Submodular Cover (SC), which is to find a minimum cost subset of a ground set $U$ such that the value of a submodular function $f$ is above a threshold $\tau$. In contrast to most existing work on SC, it is not assumed that $f$ is monotone. Two bicriteria approximation algorithms are presented for SC that, for input parameter $0 < \epsilon < 1$, give $O( 1 / \epsilon^2 )$ ratio to the optimal cost and ensures the function $f$ is at least $\tau(1 - \epsilon)/2$. A lower bound shows that under the value query model shows that no polynomial-time algorithm can ensure that $f$ is larger than $\tau/2$. Further, the algorithms presented are scalable to large data sets, processing the ground set in a stream. Similar algorithms developed for SC also work for the related optimization problem of Submodular Maximization (KCSM). Finally, the algorithms are demonstrated to be effective in experiments involving graph cut and data summarization functions.
APA
Crawford, V.. (2023). Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:9517-9537 Available from https://proceedings.mlr.press/v206/crawford23a.html.

Related Material