### Improved Smoothed Analysis of Multiobjective OptimizationImproved Smoothed Analysis of Multiobjective Optimization

Access Restriction
Subscribed

 Author Brunsch, Tobias ♦ Rglin, Heiko Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Multiobjective optimization ♦ Smoothed analysis Abstract We present several new results about smoothed analysis of multiobjective optimization problems. Motivated by the discrepancy between worst-case analysis and practical experience, this line of research has gained a lot of attention in the last decade. We consider problems in which $\textit{d}$ linear and one arbitrary objective function are to be optimized over a set $\textit{S}$ ⊆ {0, $1}^{n}$ of feasible solutions. We improve the previously best known bound for the smoothed number of Pareto-optimal solutions to $O(n^{2d}$ $&phis;^{d}),$ where &phis; denotes the perturbation parameter. Additionally, we show that for any constant $\textit{c}$ the $\textit{c}th$ moment of the smoothed number of Pareto-optimal solutions is bounded by $O((n^{2d}$ $&phis;^{d})^{c}).$ This improves the previously best known bounds significantly. Furthermore, we address the criticism that the perturbations in smoothed analysis destroy the zero-structure of problems by showing that the smoothed number of Pareto-optimal solutions remains polynomially bounded even for zero-preserving perturbations. This broadens the class of problems captured by smoothed analysis and it has consequences for nonlinear objective functions. One corollary of our result is that the smoothed number of Pareto-optimal solutions is polynomially bounded for polynomial objective functions. Our results also extend to integer optimization problems. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-03-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 1 Page Count 58 Starting Page 1 Ending Page 58

#### Open content in new tab

Source: ACM Digital Library