# Pareto Optimization for Subset Selection with Dynamic Cost Constraints

arXiv: https://arxiv.org/abs/1811.07806 · HTML: https://mlsanity.com/paper/1811.07806/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2018.

## Built on by (most cited first, 15 of 15)

- [Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2112.08581/) (2021)
- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees](https://mlsanity.com/paper/2110.09332/) (2021)
- [Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem](https://mlsanity.com/paper/2404.06014/) (2024)
- [Fast Pareto Optimization Using Sliding Window Selection](https://mlsanity.com/paper/2305.07178/) (2023)
- [Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2203.02693/) (2022)
- [Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences](https://mlsanity.com/paper/2104.09884/) (2021)
- [Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties](https://mlsanity.com/paper/2309.14359/) (2023)
- [On the use of evolutionary optimization for the dynamic chance constrained open-pit mine scheduling problem](https://mlsanity.com/paper/2604.13385/) (2026)
- [Biased Hypothesis Formation From Projection Pursuit](https://mlsanity.com/paper/2201.00889/) (2022)
- [A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2404.03838/) (2024)
- [Sliding Window 3-Objective Pareto Optimization for Problems with Chance Constraints](https://mlsanity.com/paper/2406.04899/) (2024)
- [Detection-Rate-Emphasized Multi-objective Evolutionary Feature Selection for Network Intrusion Detection](https://mlsanity.com/paper/2406.09180/) (2024)
- [Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization](https://mlsanity.com/paper/2406.13414/) (2024)
- [Pareto Data Framework: Steps Towards Resource-Efficient Decision Making Using Minimum Viable Data (MVD)](https://mlsanity.com/paper/2409.12112/) (2024)

## Abstract (arXiv)

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 φ= (αf/2)(1-frac1eαf)-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.