Abstract
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 multi-objective 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.
Funding Information
  • 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)

This publication has 29 references indexed in Scilit: