Revised: May 13, 2014
Published: September 29, 2014
Abstract: [Plain Text Version]
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).
Licensed under a Creative Commons Attribution License (CC-BY)