TY - JOUR
AU - Roostapour, Vahid
AU - Neumann, Aneta
AU - Neumann, Frank
AU - Friedrich, Tobias
PY - 2019/07/17
Y2 - 2022/08/10
TI - Pareto Optimization for Subset Selection with Dynamic Cost Constraints
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 33
IS - 01
SE - AAAI Technical Track: Heuristic Search and Optimization
DO - 10.1609/aaai.v33i01.33012354
UR - https://ojs.aaai.org/index.php/AAAI/article/view/4075
SP - 2354-2361
AB - <p>In this paper, we consider the subset selection problem for function <em>f</em> with constraint bound <em>B</em> which changes over time. We point out that adaptive variants of greedy approaches commonly used in the area of submodular optimization are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a <em>φ</em> = (<em>α</em><sub><em>f</em></sub><em>/</em>2)(1− <sub><em>α</em></sub><sup>1</sup><sub><em>f</em></sub> )-approximation, where <em>α</em><sub><em>f</em></sub> is the sub<em>e</em> modularity ratio of <em>f</em>, for each possible constraint bound <em>b</em> ≤ <em>B</em>. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that <em>B</em> increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms.</p>
ER -