*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: The Complexity of Extended Formulations
Arefin Huq
School of Computer Science
College of Computing
Georgia Institute of Technology
Date: Wednesday, May 11, 2016
Time: 11am - 2pm
Location: Klaus 2100
Committee:
Prof. Lance Fortnow (Co-advisor, SCS, Georgia Tech)
Prof. Sebastian Pokutta (Co-advisor, ISyE, Georgia Tech)
Prof. Greg Blekherman (Math, Georgia Tech)
Prof. Dick Lipton (SCS, Georgia Tech)
Prof. Santosh Vempala (SCS, Georgia Tech)
Abstract:
Combinatorial optimization plays a central role in complexity theory, operations research, and algorithms. Extended formulations give a powerful approach to solve combinatorial optimization problems: if one can find a concise geometric description of the possible solutions to a problem then one can use convex optimization to solve the problem quickly.
Many combinatorial optimization problems have a natural symmetry. In this work we explore the role of symmetry in extended formulations for combinatorial optimization, focusing on two well-known and extensively studied problems: the matching problem and the traveling salesperson problem.
In his groundbreaking work, Yannakakis showed that the matching problem does not have a small symmetric linear extended formulation. Rothvoß later showed that any linear extended formulation for matching, symmetric or not, must have exponential size. In light of this, we ask whether the matching problem has a small semidefinite extended formulation, since semidefinite programming generalizes linear programming. We show that the answer is no if the formulation is also required to be symmetric. Put simply, the matching problem does not have a small symmetric semidefinite extended formulation.
We next consider optimization over the copositive cone and its dual, the completely positive cone. Optimization in this setting is NP-hard. We present a general framework for producing compact symmetric copositive formulations for a large class of problems. We show that, in contrast to the semidefinite case, both the matching and traveling salesperson problems have small copositive formulations even if we require symmetry.
