Smoothed Analysis of Pareto Curves in Multiobjective Optimization.

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