# Smoothed Analysis of Pareto Curves in Multiobjective Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2020.

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

- [The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics](https://mlsanity.com/paper/2601.16849/) (2026)

## Abstract (arXiv)

In a multiobjective optimization problem a solution is called Pareto-optimal if no criterion can be improved without deteriorating at least one of the other criteria. Computing the set of all Pareto-optimal solutions is a common task in multiobjective optimization to filter out unreasonable trade-offs. For most problems the number of Pareto-optimal solutions increases only moderately with the input size in applications. However, for virtually every multiobjective optimization problem there exist worst-case instances with an exponential number of Pareto-optimal solutions. In order to explain this discrepancy, we analyze a large class of multiobjective optimization problems in the model of smoothed analysis and prove a polynomial bound on the expected number of Pareto-optimal solutions. We also present algorithms for computing the set of Pareto-optimal solutions for different optimization problems and discuss related results on the smoothed complexity of optimization problems.