Volume 10 (2014) Article 10 pp. 237-256
Lower Bounds for the Average and Smoothed Number of Pareto-Optima
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.