Paper detail

Lower Bounds for the Smoothed Number of Pareto optimal Solutions

In 2009, Roeglin and Teng showed that the smoothed number of Pareto optimal solutions of linear multi-criteria optimization problems is polynomially bounded in the number $n$ of variables and the maximum density $ϕ$ of the semi-random input model for any fixed number of objective functions. Their bound is, however, not very practical because the exponents grow exponentially in the number $d+1$ of objective functions. In a recent breakthrough, Moitra and O'Donnell improved this bound significantly to $O(n^{2d} ϕ^{d(d+1)/2})$. An "intriguing problem", which Moitra and O'Donnell formulate in their paper, is how much further this bound can be improved. The previous lower bounds do not exclude the possibility of a polynomial upper bound whose degree does not depend on $d$. In this paper we resolve this question by constructing a class of instances with $Ω((n ϕ)^{(d-\log{d}) \cdot (1-Θ{1/ϕ})})$ Pareto optimal solutions in expectation. For the bi-criteria case we present a higher lower bound of $Ω(n^2 ϕ^{1 - Θ{1/ϕ}})$, which almost matches the known upper bound of $O(n^2 ϕ)$.