Computer Science – Data Structures and Algorithms
Scientific paper
2010-11-10
Computer Science
Data Structures and Algorithms
21 pages
Scientific paper
Consider an optimization problem with $n$ binary variables and $d+1$ linear objective functions. Each valid solution $x \in \{0,1\}^n$ gives rise to an objective vector in $\R^{d+1}$, and one often wants to enumerate the Pareto optima among them. In the worst case there may be exponentially many Pareto optima; however, it was recently shown that in (a generalization of) the smoothed analysis framework, the expected number is polynomial in $n$. Unfortunately, the bound obtained had a rather bad dependence on $d$; roughly $n^{d^d}$. In this paper we show a significantly improved bound of $n^{2d}$. Our proof is based on analyzing two algorithms. The first algorithm, on input a Pareto optimal $x$, outputs a "testimony" containing clues about $x$'s objective vector, $x$'s coordinates, and the region of space $B$ in which $x$'s objective vector lies. The second algorithm can be regarded as a {\em speculative} execution of the first -- it can uniquely reconstruct $x$ from the testimony's clues and just \emph{some} of the probability space's outcomes. The remainder of the probability space's outcomes are just enough to bound the probability that $x$'s objective vector falls into the region $B$.
Moitra Ankur
O'Donnell Ryan
No associations
LandOfFree
Pareto Optimal Solutions for Smoothed Analysts 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 Pareto Optimal Solutions for Smoothed Analysts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pareto Optimal Solutions for Smoothed Analysts will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-613135