Show simple item record

dc.contributor.advisorFortnow, Lance
dc.contributor.advisorPokutta, Sebastian
dc.contributor.authorHuq, Arefin
dc.date.accessioned2016-08-22T12:21:37Z
dc.date.available2016-08-22T12:21:37Z
dc.date.created2016-08
dc.date.issued2016-05-13
dc.date.submittedAugust 2016
dc.identifier.urihttp://hdl.handle.net/1853/55556
dc.description.abstractCombinatorial 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.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectComputational complexity
dc.subjectCombinatorial optimization
dc.subjectExtended formulations
dc.subjectSymmetry
dc.subjectSemidefinite programming
dc.subjectCopositive programming
dc.subjectMatching problem
dc.subjectTraveling salesperson problem
dc.titleThe Complexity of Extended Formulations
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentComputer Science
thesis.degree.levelDoctoral
dc.contributor.committeeMemberBlekherman, Greg
dc.contributor.committeeMemberLipton, Richard
dc.contributor.committeeMemberVempala, Santosh
dc.date.updated2016-08-22T12:21:37Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record