期刊
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
卷 22, 期 4, 页码 595-608出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TEVC.2017.2749263
关键词
Constrained optimization; experimental studies; multiobjective evolutionary algorithms (MOEAs); submodular optimization; theoretical analysis
资金
- National Science Foundation of China [61603367, 61333014, 61672478]
- Young Elite Scientists Sponsorship Program by CAST [2016QNRC001]
- Collaborative Innovation Center of Novel Software Technology and Industrialization
- Science and Technology Innovation Committee Foundation of Shenzhen [ZDSYS201703031748284]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据