Proceedings

Fast Pareto Optimization for Subset Selection with Dynamic Cost Constraints

Chao Bian, Chao Qian, Frank Neumann, Yang Yu

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 2191-2197.

https://doi.org/10.24963/ijcai.2021/302

Keywords

  • Heuristic Search and Game Playing: Heuristic Search
  • Heuristic Search and Game Playing: Heuristic Search and Machine Learning
  • Machine Learning: Evolutionary Learning

Abstract

Subset selection with cost constraints is a fundamental problem with various applications such as influence maximization and sensor placement. The goal is to select a subset from a ground set to maximize a monotone objective function such that a monotone cost function is upper bounded by a budget. Previous algorithms with bounded approximation guarantees include the generalized greedy algorithm, POMC and EAMC, all of which can achieve the best known approximation guarantee. In real-world scenarios, the resources often vary, i.e., the budget often changes over time, requiring the algorithms to adapt the solutions quickly. However, when the budget changes dynamically, all these three algorithms either achieve arbitrarily bad approximation guarantees, or require a long running time. In this paper, we propose a new algorithm FPOMC by combining the merits of the generalized greedy algorithm and POMC. That is, FPOMC introduces a greedy selection strategy into POMC. We prove that FPOMC can maintain the best known approximation guarantee efficiently.

Chao Bian, Chao Qian, Frank Neumann, and Yang Yu. 2021. Fast Pareto Optimization for Subset Selection with Dynamic Cost Constraints. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 2191–2197. https://doi.org/10.24963/ijcai.2021/302
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards