Fast Pareto Optimization for Subset Selection with Dynamic Cost Constraints
Fast Pareto Optimization for Subset Selection with Dynamic Cost Constraints
Chao Bian, Chao Qian, Frank Neumann, Yang Yu
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 2191-2197.
https://doi.org/10.24963/ijcai.2021/302
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.
Keywords:
Machine Learning: Evolutionary Learning
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Heuristic Search and Machine Learning