| Autor: |
Heiko Röglin |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Beyond the Worst-Case Analysis of Algorithms |
| DOI: |
10.1017/9781108637435.020 |
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
