  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 subset S of {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} phi^d), where phi 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^{2d} phi^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 non-linear objective
functions. One corollary of our result is that the smoothed number of
Pareto-optimal solutions is polynomially bounded for polynomial objective
functions.
