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 $\varphi$ 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}{\varphi }^{d(d+1)\mathrm{/}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 $\mathrm{\Omega }((n\varphi {)}^{(d-\log d)\cdot (1-\mathrm{\Theta }1\mathrm{/}\varphi )})$ Pareto optimal solutions in expectation. For the bi-criteria case we present a higher lower bound of $\mathrm{\Omega }(n^2{\varphi }^{1-\mathrm{\Theta }1\mathrm{/}\varphi })$, which almost matches the known upper bound of $O(n^2\varphi )$.