Pareto optimization for subset selection with dynamic cost constraints
- We consider the subset selection problem for function f with constraint bound B that changes over time. Within the area of submodular optimization, various greedy approaches are commonly used. For dynamic environments we observe that the adaptive variants of these greedy approaches are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a phi=(alpha(f)/2)(1 - 1/e(alpha)f)-approximation, where alpha(f) is the submodularity ratio of f, for each possible constraint bound b <= B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms. We also consider EAMC, a new evolutionary algorithm with polynomial expected time guarantee to maintain phi approximation ratio, and NSGA-II with two different population sizes as advancedWe consider the subset selection problem for function f with constraint bound B that changes over time. Within the area of submodular optimization, various greedy approaches are commonly used. For dynamic environments we observe that the adaptive variants of these greedy approaches are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a phi=(alpha(f)/2)(1 - 1/e(alpha)f)-approximation, where alpha(f) is the submodularity ratio of f, for each possible constraint bound b <= B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms. We also consider EAMC, a new evolutionary algorithm with polynomial expected time guarantee to maintain phi approximation ratio, and NSGA-II with two different population sizes as advanced multi-objective optimization algorithm, to demonstrate their challenges in optimizing the maximum coverage problem. Our empirical analysis shows that, within the same number of evaluations, POMC is able to perform as good as NSGA-II under linear constraint, while EAMC performs significantly worse than all considered algorithms in most cases.…
Author details: | Vahid RoostapourORCiD, Aneta NeumannORCiD, Frank Neumann, Tobias FriedrichORCiDGND |
---|---|
DOI: | https://doi.org/10.1016/j.artint.2021.103597 |
ISSN: | 0004-3702 |
ISSN: | 1872-7921 |
Title of parent work (English): | Artificial intelligence |
Publisher: | Elsevier |
Place of publishing: | Amsterdam |
Publication type: | Article |
Language: | English |
Date of first publication: | 2022/09/09 |
Publication year: | 2022 |
Release date: | 2023/11/21 |
Tag: | Multi-objective optimization; Runtime analysis; Submodular function; Subset selection |
Volume: | 302 |
Article number: | 103597 |
Number of pages: | 17 |
Funding institution: | Australian Research Council (ARC)Australian Research Council [DP160102401]; German Science Foundation (DFG)German Research Foundation (DFG) [FR2988]; Alexander von Humboldt FoundationAlexander von Humboldt Foundation |
Organizational units: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
6 Technik, Medizin, angewandte Wissenschaften / 69 Hausbau, Bauhandwerk / 690 Hausbau, Bauhandwerk | |
Peer review: | Referiert |