Back to search

Georgia Institute of Technology

The Complexity of Extended Formulations

Abstract

dc:description.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 [1991, 1988] showed that the matching problem does not have a small symmetric linear extended formulation. Rothvoß [2014] 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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Huq, Arefin
Advisors dc:contributor.advisor
  • Fortnow, Lance
  • Pokutta, Sebastian
Committee members dc:contributor.committeemember
  • Blekherman, Greg
  • Lipton, Richard
  • Vempala, Santosh

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/55556

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Huq, Arefin. The Complexity of Extended Formulations. Doctoral thesis, Georgia Institute of Technology, 2016. http://hdl.handle.net/1853/55556