Computer Science – Data Structures and Algorithms
Scientific paper
2010-12-06
Computer Science
Data Structures and Algorithms
Scientific paper
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 $\phi$ 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} \phi^{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 $\Omega ((n \phi)^{(d-\log{d}) \cdot (1-\Theta{1/\phi})})$ Pareto optimal solutions in expectation. For the bi-criteria case we present a higher lower bound of $\Omega (n^2 \phi^{1 - \Theta{1/\phi}})$, which almost matches the known upper bound of $O(n^2 \phi)$.
Brunsch Tobias
Roeglin Heiko
No associations
LandOfFree
Lower Bounds for the Smoothed Number of Pareto optimal Solutions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lower Bounds for the Smoothed Number of Pareto optimal Solutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds for the Smoothed Number of Pareto optimal Solutions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-167777