.png){kind=icon}
.png){kind=icon}
Return
Constrained Monotone k-Submodular Function Maximization Using Multiobjective Evolutionary Algorithms With Theoretical Guarantee
.png){kind=icon}
PRE
AI
DOI：10.1109/TEVC.2017.2749263.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The problem of maximizing monotone k-submodular functions under a size constraint arises in many applications, and it is NP-hard. In this paper, we propose a new approach which employs a multiobjective evolutionary algorithm to maximize the given objective and minimize the size simultaneously. For general cases, we prove that the proposed method can obtain the asymptotically tight approximation guarantee, which was also achieved by the greedy algorithm. Moreover, we further give instances where the proposed approach performs better than the greedy algorithm on applications of influence maximization, information coverage maximization, and sensor placement. Experimental results on real-world data sets exhibit the superior performance of the proposed approach.
Keywords:
Constrained optimization
experimental studies
multiobjective evolutionary algorithms (MOEAs)
submodular optimization
theoretical analysis
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
12
Papers:
1.8K
Citations:
2.4W
Organization
View more organizations