Maximization of Monotone $k$-Submodular Functions with Bounded Curvature and Non-$k$-Submodular Functions

Tatsuya Matsuoka, Naoto Ohsaka
Proceedings of The 13th Asian Conference on Machine Learning, PMLR 157:1707-1722, 2021.

Abstract

The concept of $k$-submodularity is an extension of submodularity, of which maximization has various applications, such as influence maximization and sensor placement. In such situations, to model complicated real problems, we want to deal with multiple factors, such as, more detailed parameter representing a property of a given function or a constraint which should be imposed for a given function, simultaneously. Besides, it is preferable that an algorithm for the modeling problem is simple. In this paper, for both monotone $k$-submodular function maximization with bounded curvature and monotone weakly $k$-submodular function maximization, we give approximation ratio analysis on greedy-type algorithms on the problem with the matroid constraint and that with the individual size constraint. Furthermore, we give an approximation ratio analysis on another type of the relaxation of $k$-submodular functions, approximately $k$-submodular functions, with the matroid constraint.

Cite this Paper

BibTeX
@InProceedings{pmlr-v157-matsuoka21b, title = {Maximization of Monotone $k$-Submodular Functions with Bounded Curvature and Non-$k$-Submodular Functions}, author = {Matsuoka, Tatsuya and Ohsaka, Naoto}, booktitle = {Proceedings of The 13th Asian Conference on Machine Learning}, pages = {1707--1722}, year = {2021}, editor = {Balasubramanian, Vineeth N. and Tsang, Ivor}, volume = {157}, series = {Proceedings of Machine Learning Research}, month = {17--19 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v157/matsuoka21b/matsuoka21b.pdf}, url = {https://proceedings.mlr.press/v157/matsuoka21b.html}, abstract = {The concept of $k$-submodularity is an extension of submodularity, of which maximization has various applications, such as influence maximization and sensor placement. In such situations, to model complicated real problems, we want to deal with multiple factors, such as, more detailed parameter representing a property of a given function or a constraint which should be imposed for a given function, simultaneously. Besides, it is preferable that an algorithm for the modeling problem is simple. In this paper, for both monotone $k$-submodular function maximization with bounded curvature and monotone weakly $k$-submodular function maximization, we give approximation ratio analysis on greedy-type algorithms on the problem with the matroid constraint and that with the individual size constraint. Furthermore, we give an approximation ratio analysis on another type of the relaxation of $k$-submodular functions, approximately $k$-submodular functions, with the matroid constraint.} }
Endnote
%0 Conference Paper %T Maximization of Monotone $k$-Submodular Functions with Bounded Curvature and Non-$k$-Submodular Functions %A Tatsuya Matsuoka %A Naoto Ohsaka %B Proceedings of The 13th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Vineeth N. Balasubramanian %E Ivor Tsang %F pmlr-v157-matsuoka21b %I PMLR %P 1707--1722 %U https://proceedings.mlr.press/v157/matsuoka21b.html %V 157 %X The concept of $k$-submodularity is an extension of submodularity, of which maximization has various applications, such as influence maximization and sensor placement. In such situations, to model complicated real problems, we want to deal with multiple factors, such as, more detailed parameter representing a property of a given function or a constraint which should be imposed for a given function, simultaneously. Besides, it is preferable that an algorithm for the modeling problem is simple. In this paper, for both monotone $k$-submodular function maximization with bounded curvature and monotone weakly $k$-submodular function maximization, we give approximation ratio analysis on greedy-type algorithms on the problem with the matroid constraint and that with the individual size constraint. Furthermore, we give an approximation ratio analysis on another type of the relaxation of $k$-submodular functions, approximately $k$-submodular functions, with the matroid constraint.
APA
Matsuoka, T. & Ohsaka, N.. (2021). Maximization of Monotone $k$-Submodular Functions with Bounded Curvature and Non-$k$-Submodular Functions. Proceedings of The 13th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 157:1707-1722 Available from https://proceedings.mlr.press/v157/matsuoka21b.html.

Related Material