Pareto Optimal Solutions for Smoothed Analysts Ankur Moitra, IAS joint work with Ryan O’Donnell, CMU September 26, 2011 AnkurMoitra (IAS) Pareto September26,2011 values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n e u l a v W − weight values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n e u l a v W − weight values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n e u l a v W − weight values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n Not Pareto Optimal e u l a v W − weight values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n Pareto Optimal! e u l a v W − weight values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n e u l a v W − weight values v ... v v ... v W 1 i i+1 n weights w ... w w ... w 1 i i+1 n e u PO(i) l a v W − weight