Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/138632
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Pareto optimization for subset selection with dynamic cost constraints |
Author: | Roostapour, V. Neumann, A. Neumann, F. Friedrich, T. |
Citation: | Artificial Intelligence, 2022; 302(2022):103597-1-103597-17 |
Publisher: | Elsevier |
Issue Date: | 2022 |
ISSN: | 0004-3702 1872-7921 |
Statement of Responsibility: | Vahid Roostapour, Aneta Neumann, Frank Neumann, Tobias Friedrich |
Abstract: | 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 [Formula presented]-approximation, where α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 ϕ 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. |
Keywords: | Subset selection; Submodular function; Multi-objective optimization; Runtime analysis |
Description: | Available online 9 September 2021 |
Rights: | © 2021 Elsevier B.V. All rights reserved. |
DOI: | 10.1016/j.artint.2021.103597 |
Grant ID: | http://purl.org/au-research/grants/arc/DP160102401 |
Published version: | https://doi.org/10.1016/j.artint.2021.103597 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.