Size-constrained k-submodular maximization in near-linear time

Guanyu Nie, Yanhui Zhu, Yididiya Y. Nadew, Samik Basu, A. Pavan, Christopher John Quinn
Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, PMLR 216:1545-1554, 2023.

Abstract

We investigate the problems of maximizing k-submodular functions over total size constraints and over individual size constraints. k-submodularity is a generalization of submodularity beyond just picking items of a ground set, instead associating one of k types to chosen items. For sensor selection problems, for instance, this enables modeling of which type of sensor to put at a location, not simply whether to put a sensor or not. We propose and analyze threshold-greedy algorithms for both types of constraints. We prove that our proposed algorithms achieve the best known approximation ratios for both constraint types, up to a user-chosen parameter that balances computational complexity and the approximation ratio, while only using a number of function evaluations that depends linearly (up to poly-logarithmic terms) on the number of elements n, the number of types k, and the inverse of the user chosen parameter. Other algorithms that achieve the best-known deterministic approximation ratios require a number of function evaluations that depends linearly on the budget B, while our methods do not. We empirically demonstrate our algorithms’ performance in applications of sensor placement with k types and influence maximization with k topics.

Cite this Paper

BibTeX
@InProceedings{pmlr-v216-nie23a, title = {Size-constrained k-submodular maximization in near-linear time}, author = {Nie, Guanyu and Zhu, Yanhui and Nadew, Yididiya Y. and Basu, Samik and Pavan, A. and Quinn, Christopher John}, booktitle = {Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence}, pages = {1545--1554}, 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/nie23a/nie23a.pdf}, url = {https://proceedings.mlr.press/v216/nie23a.html}, abstract = {We investigate the problems of maximizing k-submodular functions over total size constraints and over individual size constraints. k-submodularity is a generalization of submodularity beyond just picking items of a ground set, instead associating one of k types to chosen items. For sensor selection problems, for instance, this enables modeling of which type of sensor to put at a location, not simply whether to put a sensor or not. We propose and analyze threshold-greedy algorithms for both types of constraints. We prove that our proposed algorithms achieve the best known approximation ratios for both constraint types, up to a user-chosen parameter that balances computational complexity and the approximation ratio, while only using a number of function evaluations that depends linearly (up to poly-logarithmic terms) on the number of elements n, the number of types k, and the inverse of the user chosen parameter. Other algorithms that achieve the best-known deterministic approximation ratios require a number of function evaluations that depends linearly on the budget B, while our methods do not. We empirically demonstrate our algorithms’ performance in applications of sensor placement with k types and influence maximization with k topics.} }
Endnote
%0 Conference Paper %T Size-constrained k-submodular maximization in near-linear time %A Guanyu Nie %A Yanhui Zhu %A Yididiya Y. Nadew %A Samik Basu %A A. Pavan %A Christopher John Quinn %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-nie23a %I PMLR %P 1545--1554 %U https://proceedings.mlr.press/v216/nie23a.html %V 216 %X We investigate the problems of maximizing k-submodular functions over total size constraints and over individual size constraints. k-submodularity is a generalization of submodularity beyond just picking items of a ground set, instead associating one of k types to chosen items. For sensor selection problems, for instance, this enables modeling of which type of sensor to put at a location, not simply whether to put a sensor or not. We propose and analyze threshold-greedy algorithms for both types of constraints. We prove that our proposed algorithms achieve the best known approximation ratios for both constraint types, up to a user-chosen parameter that balances computational complexity and the approximation ratio, while only using a number of function evaluations that depends linearly (up to poly-logarithmic terms) on the number of elements n, the number of types k, and the inverse of the user chosen parameter. Other algorithms that achieve the best-known deterministic approximation ratios require a number of function evaluations that depends linearly on the budget B, while our methods do not. We empirically demonstrate our algorithms’ performance in applications of sensor placement with k types and influence maximization with k topics.
APA
Nie, G., Zhu, Y., Nadew, Y.Y., Basu, S., Pavan, A. & Quinn, C.J.. (2023). Size-constrained k-submodular maximization in near-linear time. Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 216:1545-1554 Available from https://proceedings.mlr.press/v216/nie23a.html.

Related Material