Computer Science/Discrete Mathematics Seminar I

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.