Smoothed Analysis of Pareto Curves in Multiobjective Optimization
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{roglin2020smoothed,
author = {Heiko Röglin},
title = {{Smoothed Analysis of Pareto Curves in Multiobjective Optimization}},
booktitle = {Beyond the Worst-Case Analysis of Algorithms},
year = {2020},
url = {https://openreview.net/forum?id=Ib6Ksmsn6i9},
}Loading related content...