Constrained Monotone $k$ -Submodular Function Maximization Using Multiobjective Evolutionary Algorithms With Theoretical Guarantee
- 6 September 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 22 (4) , 595-608
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.Keywords
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:
- Social dynamics of DiggEPJ Data Science, 2012
- Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective ModelsEvolutionary Computation, 2010
- Computing Minimum Cuts by Randomized Search HeuristicsAlgorithmica, 2009
- Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimizationMathematical Programming, 2008
- Accelerated greedy algorithms for maximizing submodular set functions2005
- A Generic Framework for Constrained Optimization Using Genetic AlgorithmsIEEE Transactions on Evolutionary Computation, 2005
- Running Time Analysis of Multiobjective Evolutionary Algorithms on Pseudo-Boolean FunctionsIEEE Transactions on Evolutionary Computation, 2004
- A fast and elitist multiobjective genetic algorithm: NSGA-IIIEEE Transactions on Evolutionary Computation, 2002
- An efficient constraint handling method for genetic algorithmsComputer Methods in Applied Mechanics and Engineering, 2000
- A threshold of ln n for approximating set coverJournal of the ACM, 1998