Journal Home > Volume 28 , Issue 5
Tsinghua Science and Technology 2023, 28(5): 896-905 https://doi.org/10.26599/TST.2022.9010039
Open Access | Issue | Published: 19 May 2023

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

Show Author's Information Qian Liu1,  Kemin Yu1,  Min Li1,  Yang Zhou1( )
School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China
Keywords:
approximation algorithm, k-submodularity, knapsack constraint, matroid constraint
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
Download citation
EndNote(RIS)
BibTeX

526

Views

89

Downloads

Citations

2

Crossref

1

WoS

1

Scopus

0

CSCD

Abstract Full text About this article

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.


menu
Abstract
Full text
Outline
About this article

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

Show Author's information Qian Liu1, Kemin Yu1, Min Li1, Yang Zhou1( )
School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China

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: approximation algorithm, k-submodularity, knapsack constraint, matroid constraint

References(17)

[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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 20 May 2022
Revised: 21 July 2022
Accepted: 10 September 2022
Published: 19 May 2023
Issue date: October 2023

Copyright

© The author(s) 2023.

Acknowledgements

This paper was supported by the Natural Science Foundation of Shandong Province of China (Nos. ZR2020MA029 and ZR2021MA100) and the National Natural Science Foundation of China (No. 12001335).

Rights and permissions

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