Smoothed Analysis of Multiobjective Optimization

optimization problems is to enumerate the set of Pareto-optimal
solutions. The heuristics following this principle are often successful
in practice, even though the number of Pareto-optimal solutions can be
exponential in the worst case.

We analyze multiobjective optimization problems in the framework of
smoothed analysis, which is based on a semi-random input model in which
an adversary can specify an input which is subsequently slightly
perturbed at random.

We prove that the smoothed number of Pareto-optimal solutions in any
multiobjective binary optimization problem with a finite number of
linear objective functions is polynomial. Moreover, we give polynomial
bounds on all finite moments of the number of Pareto-optimal solutions,
which yields the first non-trivial concentration bound for this quantity.

This talk is based on joint work with Shang-Hua Teng.