AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (2.4 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints

School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China
Show Author Information

Abstract

A k-submodular function is a generalization of a submodular function, its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets. The k-submodular maximization problem has a wide range of applications. In this paper, we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.

References

[1]
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, An analysis of approximations for maximizing submodular set functions-I, Math. Program., vol. 14, no. 1, pp. 265294, 1978.
[2]
M. Sviridenko, A note on maximizing a submodular set function subject to a knapsack constraint, Oper. Res. Lett., vol. 32, no. 1, pp. 4143, 2004.
[3]
A. Ene and H. L. Nguyên, A nearly-linear time algorithm for submodular maximization with a knapsack constraint, in Proc. 46th Int. Colloquium on Automata, Languages, and Programming, Patras, Greece, 2019, pp. 53:153:12.
[4]
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, Maximizing a monotone submodular function subject to a matroid constraint, SIAM J. Comput., vol. 40, no. 6, pp. 17401766, 2011.
[5]
Y. Filmus and J. Ward, Monotone submodular maximization over a matroid via non-oblivious local search, SIAM J. Comput., vol. 43, no. 2, pp. 514542, 2014.
[6]
K. K. Sarpatwar, B. Schieber, and H. Shachnai, Constrained submodular maximization via greedy local search, Oper. Res. Lett., vol. 47, no. 1, pp. 16, 2019.
[7]
A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, Guarantees for greedy maximization of non-submodular functions with applications, in Proc. 34th Int. Conf. Machine Learning, Sydney, Australia, 2017, pp. 498507.
[8]
M. Feldman, Maximization problems with submodular objective functions, PhD dissertation, Computer Science Department, Technion, Haifa, Israel, 2013.
[9]
C. C. Huang, N. Kakimura, S. Mauras, and Y. Yoshida, Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model, SIAM J. Discrete Math., vol. 36, no. 1, pp. 355382, 2022.
[10]
Z. C. Liu, L. K. Guo, D. L. Du, D. C. Xu, and X. Y. Zhang, Maximization problems of balancing submodular relevance and supermodular diversity, J. Glob. Optim., vol. 82, no. 1, pp. 179194, 2022.
[11]
Y. Yoshida, Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint, SIAMJ. Discrete Math., vol. 33, no. 3, pp. 14521471, 2019.
[12]
N. Ohsaka and Y. Yoshida, Monotone k-submodular function maximization with size constraints, in Proc. 28th Int. Conf. Neural Information Processing Systems, Montreal, Canada, 2015, pp. 694702.
[13]
A. Rafiey and Y. Yoshida. Fast and private submodular and k-submodular functions maximization with matroid constraints, in Proc. 37th Int. Conf. Machine Learning, Virtual event, 2020, p. 731, 2020.
[14]
J. Ward and S. Živný, Maximizing k-submodular functions and beyond, ACM Trans. Algorithms, vol. 12, no. 4, p. 47, 2016.
[15]
S. Iwata, S. I. Tanigawa, and Y. Yoshida, Improved approximation algorithms for k-submodular function maximization, in Proc. 27th Ann. ACM-SIAM Symp. Discrete Algorithms, Arlington, VA, USA, 2016, pp. 404413.
[16]
S. Sakaue, On maximizing a monotone k-submodular function subject to a matroid constraint, Discrete Optim., vol. 23, pp. 105113, 2017.
[17]
Z. Z. Tang, C. H. Wang, and H. Chan, On maximizing a monotone k-submodular function under a knapsack constraint, Oper. Res. Lett., vol. 50, no. 1, pp. 2831, 2022.
Tsinghua Science and Technology
Pages 896-905
Cite this article:
Liu Q, Yu K, Li M, et al. k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints. Tsinghua Science and Technology, 2023, 28(5): 896-905. https://doi.org/10.26599/TST.2022.9010039

803

Views

98

Downloads

4

Crossref

2

Web of Science

3

Scopus

0

CSCD

Altmetrics

Received: 20 May 2022
Revised: 21 July 2022
Accepted: 10 September 2022
Published: 19 May 2023
© The author(s) 2023.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return