
arXiv: 1111.1546
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 d linear and one arbitrary objective function are to be optimized over a set 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 2 d φ d ), where φ denotes the perturbation parameter. Additionally, we show that for any constant c the c th moment of the smoothed number of Pareto-optimal solutions is bounded by O (( n 2 d φ 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.
FOS: Computer and information sciences, Analysis of algorithms and problem complexity, Computer Science - Data Structures and Algorithms, Integer programming, multiobjective optimization, Data Structures and Algorithms (cs.DS), Multi-objective and goal programming, smoothed analysis
FOS: Computer and information sciences, Analysis of algorithms and problem complexity, Computer Science - Data Structures and Algorithms, Integer programming, multiobjective optimization, Data Structures and Algorithms (cs.DS), Multi-objective and goal programming, smoothed analysis
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 15 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
