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.