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
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.4 MB)
Cite
EndNote(RIS) BibTeX
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.

Keywords

k-submodularmatroid constraintdeterministic algorithmrandomized algorithmstreaming algorithm

References

【1】
【1】
 
 
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 6,
December 2024
Pages 1633-1641
DOI: 10.26599/TST.2023.9010122

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Cite this Report
Close
Close
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

1921

Views

299

Downloads

5

Crossref

2

Web of Science

4

Scopus

0

CSCD
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/).