Strong reductions for extended formulations

ACO Student Seminar
Friday, February 26, 2016 - 13:05
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
We generalize the existing reduction mechanism due to Braun, Pokutta and Zink (2014)for linear programming problems and semidefinite programming problems in two ways  1) relaxing the requirement of affineness2) extending to fractional optimization problems  As applications we prove several new LP-hardness and SDP-hardnessresults, e.g., for the (non-uniform) Sparsest Cut problem with bounded treewidth on the supply graph, the Balanced Separator problem with bounded treewidth onthe demand graph, the Max Cut problem and the Matching problem on 3-regular graphs.We also provide a new, very strong Lasserre integrality gapfor the Independent Set problem, which is strictly greater than thebest known LP approximation, showing that the Lasserre hierarchydoes not always provide the tightest SDP relaxation.Joint work with Gabor Braun and Sebastian Pokutta.