Home Tsinghua Science and Technology Article
PDF (2.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
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.

Keywords

k-submodularityknapsack constraintmatroid constraintapproximation algorithm

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. 265–294, 1978.
Crossref Google Scholar
[2]
M. Sviridenko, A note on maximizing a submodular set function subject to a knapsack constraint, Oper. Res. Lett., vol. 32, no. 1, pp. 41–43, 2004.
Crossref Google Scholar
[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:1–53:12.
Google Scholar
[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. 1740–1766, 2011.
Crossref Google Scholar
[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. 514–542, 2014.
Crossref Google Scholar
[6]
K. K. Sarpatwar, B. Schieber, and H. Shachnai, Constrained submodular maximization via greedy local search, Oper. Res. Lett., vol. 47, no. 1, pp. 1–6, 2019.
Crossref Google Scholar
[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. 498–507.
Google Scholar
[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. 355–382, 2022.
Crossref Google Scholar
[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. 179–194, 2022.
Crossref Google Scholar
[11]
Y. Yoshida, Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint, SIAMJ. Discrete Math., vol. 33, no. 3, pp. 1452–1471, 2019.
Crossref Google Scholar
[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. 694–702.
Google Scholar
[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.
Google Scholar
[14]
J. Ward and S. Živný, Maximizing k-submodular functions and beyond, ACM Trans. Algorithms, vol. 12, no. 4, p. 47, 2016.
Crossref Google Scholar
[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. 404–413.
Crossref Google Scholar
[16]
S. Sakaue, On maximizing a monotone k-submodular function subject to a matroid constraint, Discrete Optim., vol. 23, pp. 105–113, 2017.
Crossref Google Scholar
[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. 28–31, 2022.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 28 Issue 5,
October 2023
Pages 896-905
DOI: 10.26599/TST.2022.9010039
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
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return