| Jiang Yanjun (姜燕君)*,Wang Yijing**,Yang Ruiqi***,Li Ali****.[J].高技术通讯(英文),2026,32(1):73~83 |
|
| Maximization of monotone non-k-submodular set function with noise under matroid constraints |
| |
| DOI：10. 3772 / j. issn. 1006-6748. 2026. 01. 008 |
| 中文关键词: |
| 英文关键词: k-submodular set function, greedy, matroid constraints, approximation algorithm |
| 基金项目: |
| Author Name | Affiliation | | Jiang Yanjun (姜燕君)* | (* School of Mathematics and Statistics Science, Ludong University, Yantai 264025, P. R. China)
(** Center for Strategic Assessment and Consulting, Academy of Military Science, Beijing 100091, P. R. China)
(*** Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, P. R. China)
(**** College of Computer Science and Artificial Intelligence, Ludong University, Yantai 264025, P. R. China) | | Wang Yijing** | | | Yang Ruiqi*** | | | Li Ali**** | |
|
| Hits: 26 |
| Download times: 24 |
| 中文摘要: |
| |
| 英文摘要: |
| Submodular optimization is primarily applied in multi-agent systems for tasks such as resource allocation, task assignment, collaborative decision-making, and optimization problems. Maximization of optimizing submodular set functions attracts much attention since the 1970s. A large body of work has been done using approximation algorithms. When the dimension of the independent variable of the set function changes from one to k, it is called a k-submodular set function. The k-submodular set function, a generalization of the classical submodular set function, arises in diverse fields with varied applications. In many practical scenarios, quantifying the degree of closeness to submodularity becomes essential, leading to concepts such as approximately submodular set functions and the diminishing-return (DR) ratio. This paper investigates a k-dimensional set function under matroid constraints, which may lack full submodularity. Instead, we focus on an approximately non-k-submodular set function characterized by its DR ratio. Employing a greedy algorithmic approach, we derive an approximation guarantee for this problem. Notably, when the DR ratio is set to one, our results align with existing findings in the literature. Experimental results demonstrate the superiority of our algorithm over the baselines. |
|
View Full Text
View/Add Comment Download reader |
| Close |
|
|
|
