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.