An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints

Authors

  • Chao Bian Nanjing University
  • Chao Feng University of Science and Technology of China
  • Chao Qian Nanjing University
  • Yang Yu Nanjing University

DOI:

https://doi.org/10.1609/aaai.v34i04.5726

Abstract

In this paper, we study the problem of selecting a subset from a ground set to maximize a monotone objective function f such that a monotone cost function c is bounded by an upper limit. State-of-the-art algorithms include the generalized greedy algorithm and POMC. The former is an efficient fixed time algorithm, but the performance is limited by the greedy nature. The latter is an anytime algorithm that can find better subsets using more time, but without any polynomial-time approximation guarantee. In this paper, we propose a new anytime algorithm EAMC, which employs a simple evolutionary algorithm to optimize a surrogate objective integrating f and c. We prove that EAMC achieves the best known approximation guarantee in polynomial expected running time. Experimental results on the applications of maximum coverage, influence maximization and sensor placement show the excellent performance of EAMC.

Downloads

Published

2020-04-03

How to Cite

Bian, C., Feng, C., Qian, C., & Yu, Y. (2020). An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 3267-3274. https://doi.org/10.1609/aaai.v34i04.5726

Issue

Section

AAAI Technical Track: Machine Learning