Maximizing submodular functions under submodular constraints

Madhavan R. Padmanabhan, Yanhui Zhu, Samik Basu, A. Pavan
Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, PMLR 216:1618-1627, 2023.

Abstract

We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: SCSKC and DiffC. Given two submodular functions f and g where f is monotone, the objective of SCSKC problem is to find a set S of size at most k that maximizes f(S) under the constraint that g(S) < theta, for a given value of theta. The problem of DiffC focuses on finding a set S of size at most k such that h(S) = f(S)-g(S) is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve data-dependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of SCSKC, we prove that the greedy algorithm produces a solution whose value is at least (1-1/e)f(OPT) - A, where A is the data-dependent additive error. For the DiffC problem, we design an algorithm that uses the SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least (1-1/e)h(OPT)-B, where B is also a data-dependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced.

Cite this Paper

BibTeX
@InProceedings{pmlr-v216-padmanabhan23a, title = {Maximizing submodular functions under submodular constraints}, author = {Padmanabhan, Madhavan R. and Zhu, Yanhui and Basu, Samik and Pavan, A.}, booktitle = {Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence}, pages = {1618--1627}, year = {2023}, editor = {Evans, Robin J. and Shpitser, Ilya}, volume = {216}, series = {Proceedings of Machine Learning Research}, month = {31 Jul--04 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v216/padmanabhan23a/padmanabhan23a.pdf}, url = {https://proceedings.mlr.press/v216/padmanabhan23a.html}, abstract = {We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: SCSKC and DiffC. Given two submodular functions f and g where f is monotone, the objective of SCSKC problem is to find a set S of size at most k that maximizes f(S) under the constraint that g(S) < theta, for a given value of theta. The problem of DiffC focuses on finding a set S of size at most k such that h(S) = f(S)-g(S) is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve data-dependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of SCSKC, we prove that the greedy algorithm produces a solution whose value is at least (1-1/e)f(OPT) - A, where A is the data-dependent additive error. For the DiffC problem, we design an algorithm that uses the SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least (1-1/e)h(OPT)-B, where B is also a data-dependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced.} }
Endnote
%0 Conference Paper %T Maximizing submodular functions under submodular constraints %A Madhavan R. Padmanabhan %A Yanhui Zhu %A Samik Basu %A A. Pavan %B Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2023 %E Robin J. Evans %E Ilya Shpitser %F pmlr-v216-padmanabhan23a %I PMLR %P 1618--1627 %U https://proceedings.mlr.press/v216/padmanabhan23a.html %V 216 %X We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: SCSKC and DiffC. Given two submodular functions f and g where f is monotone, the objective of SCSKC problem is to find a set S of size at most k that maximizes f(S) under the constraint that g(S) < theta, for a given value of theta. The problem of DiffC focuses on finding a set S of size at most k such that h(S) = f(S)-g(S) is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve data-dependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of SCSKC, we prove that the greedy algorithm produces a solution whose value is at least (1-1/e)f(OPT) - A, where A is the data-dependent additive error. For the DiffC problem, we design an algorithm that uses the SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least (1-1/e)h(OPT)-B, where B is also a data-dependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced.
APA
Padmanabhan, M.R., Zhu, Y., Basu, S. & Pavan, A.. (2023). Maximizing submodular functions under submodular constraints. Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 216:1618-1627 Available from https://proceedings.mlr.press/v216/padmanabhan23a.html.

Related Material