Pareto Optimal Solutions for Smoothed Analysts

Ankur Moitra, Ryan O'Donnell

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…