Theory of Computing
-------------------
Title : Lower Bounds for the Average and Smoothed Number of Pareto-Optima
Authors : Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Roeglin
Volume : 10
Number : 10
Pages : 237-256
URL : https://theoryofcomputing.org/articles/v010a010
Abstract
--------
Smoothed analysis of multiobjective $0$--$1$ linear optimization has
drawn considerable attention recently. The goal is to give bounds for
the number of Pareto-optimal solutions (i.e., solutions with the
property that no other solution is at least as good in all the
coordinates and better in at least one) for multiobjective
optimization problems. In this article we prove several lower bounds
for the expected number of Pareto optima. Our basic result is a lower
bound of $\Omega_d(n^{d-1})$ for optimization problems with $d$
objectives and $n$ variables under fairly general conditions on the
distributions of the linear objectives. Our proof relates the problem
of finding lower bounds on the number of Pareto optima to results in
discrete geometry and geometric probability about arrangements of
hyperplanes. We use our basic result to derive the following results:
(1) To our knowledge, the first lower bound for natural multiobjective
optimization problems. We illustrate this on the maximum spanning tree
problem with randomly chosen edge weights. Our technique is
sufficiently flexible to yield such lower bounds also for other
standard objective functions studied in this setting (such as
multiobjective shortest path, TSP, matching). (2) A smoothed lower
bound of $\min \{ \Omega_d(n^{d-1.5} \phi^d), 2^{\Theta_d(n)} \}$ for
$\phi$-smooth instances of the $0$--$1$ knapsack problem with $d$
profits.
Preliminary versions of parts of this paper appeared in the
Proceedings of the 8th Annual Conference on Theory and Applications of
Models of Computation (TAMC'11)
and the Proceedings of the 32nd Annual Conference on Foundations of
Software Technology
and Theoretical Computer Science (FSTTCS'12).