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 (1.4 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Approximation Algorithms for Maximization of k-Submodular Function Under a Matroid Constraint

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

Abstract

In this paper, we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint. In order to reduce the complexity of this algorithm, we also present a randomized 1/3-approximation algorithm with the probability of 1ε, where ε is the probability of algorithm failure. Moreover, we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.

References

[1]
Y. Sun, Y. Liu, and M. Li, Maximization of k-submodular function with a matroid constraint, in Proc. 17th Annual Conference of Theory and Applications of Models of Computation, Tianjin, China, 2022, pp. 1−10.
[2]

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.

[3]

J. Ward and S. Živný, Maximizing k-submodular functions and beyond, ACM Trans. Algorithms, vol. 12, no. 4, pp. 1–26, 2016.

[4]
S. Iwata, S. Tanigawa, and Y. Yoshida, Improved approximation algorithms for k-submodular function maximization, in Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA, 2016, pp. 404–413.
[5]

H. Oshima, Improved randomized algorithm for k-submodular function maximization, SIAM J. Discrete Math., vol. 35, no. 1, pp. 1–22, 2021.

[6]
N. Ohsaka and Y. Yoshida, Monotone k-submodular function maximization with size constraints, in Proc. 28th International Conference on Neural Information Processing Systems, Montreal, Canada, 2015, pp. 694–702.
[7]
L. N. Nguyen and M. T. Thai, Streaming k-submodular maximization under noise subject to size constraint, in Proc. 37th International Conference on Machine Learning, Virtual Event, 2020, pp. 7338–7347.
[8]

Z. Tang, C. 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.

[9]

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.

[10]

S. Fujishige and S. Iwata, Bisubmodular function minimization, SIAM J. Discrete Math., vol. 19, no. 4, pp. 1065–1073, 2005.

[11]
A. Huber and V. Kolmogorov, Towards minimizing k-submodular functions, in Proc. of the Second international conference on Combinatorial Optimization, Athens, Greece, 2012, pp. 451−462.
[12]
C. Pham, Q. Vu, D. Ha, and T. Nguyen, Streaming algorithms for budgeted k-submodular maximization problem, in Proc. 10th International Conference on Computational Data and Social Networks, Virtual Event, 2021, pp. 27–38.
[13]
A. Rafiey and Y. Yoshida, Fast and private submodular and k-submodular functions maximization with matroid constraints, in Proc. 37th International Conference on Machine Learning, Virtual Event, 2020, pp. 7887–7897.
[14]

Z. Tang, C. Wang, and H. Chan, Monotone k-submodular secretary problems: Cardinality and knapsack constraints, Theor. Comput. Sci., vol. 921, pp. 86–99, 2022.

[15]
B. Korte and J. Vygen, Combinatorial Optimization : Theory and Algorithms. Berlin, Germany: Springer, 2012.
[16]
C. Chekuri, S. Gupta, and K. Quanrud, Streaming algorithms for submodular function maximization, in Proc. 42nd International Colloquium, ICALP 2015, Kyoto, Japan, 2015, pp. 318–330.
Tsinghua Science and Technology
Pages 1633-1641
Cite this article:
Liu Y, Sun Y, Li M. Approximation Algorithms for Maximization of k-Submodular Function Under a Matroid Constraint. Tsinghua Science and Technology, 2024, 29(6): 1633-1641. https://doi.org/10.26599/TST.2023.9010122

193

Views

56

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics

Received: 16 January 2023
Revised: 31 May 2023
Accepted: 11 September 2023
Published: 20 June 2024
© The Author(s) 2024.

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