  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.
