Size-constrained k-submodular maximization in near-linear time
Guanyu Nie, Yanhui Zhu, Yididiya Y. Nadew, Samik Basu, A. Pavan, Christopher John Quinn
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.
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.}
}