Pareto Optimal Solutions for Smooth Analysts

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I
Topic:Pareto Optimal Solutions for Smooth Analysts
Speaker:Ryan O'Donnell
Affiliation:Carnegie Mellon University; Member, School of Mathematics
Date:Monday, March 21
Time/Room:11:15am - 12:15pm/West Bldg. Lecture Hall

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 these. 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 involves a novel use of the union bound. This is joint work with Ankur Moitra of MIT.