ML Anthology

Pareto Optimization for Subset Selection with Dynamic Cost Constraints

Vahid Roostapour, Aneta Neumann, Frank Neumann, Tobias Friedrich
AAAI 2019 pp. 2354-2361
doi:10.1609/AAAI.V33I01.33012354 /aaai/2019/roostapour2019aaai-pareto/

Abstract

In this paper, we consider the subset selection problem for function f with constraint bound B 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 φ = (αf/2)(1− α1f )-approximation, where αf is the sube modularity 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.

PDF AAAI Semantic Scholar

Cite

Text

Roostapour et al. "Pareto Optimization for Subset Selection with Dynamic Cost Constraints." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33012354

Markdown

[Roostapour et al. "Pareto Optimization for Subset Selection with Dynamic Cost Constraints." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/roostapour2019aaai-pareto/) doi:10.1609/AAAI.V33I01.33012354

BibTeX

@inproceedings{roostapour2019aaai-pareto,
  title     = {{Pareto Optimization for Subset Selection with Dynamic Cost Constraints}},
  author    = {Roostapour, Vahid and Neumann, Aneta and Neumann, Frank and Friedrich, Tobias},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {2354-2361},
  doi       = {10.1609/AAAI.V33I01.33012354},
  url       = {https://mlanthology.org/aaai/2019/roostapour2019aaai-pareto/}
}