English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Symmetry Matters for Sizes of Extended Formulations

Kaibel, V., Pashkovich, K., & Theis, D. O. (2010). Symmetry Matters for Sizes of Extended Formulations. In Integer Programming and Combinatorial Optimization (pp. 135-148).

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kaibel, V.1, Author
Pashkovich, Kanstantsin1, 2, Author           
Theis, D. O.1, Author
Affiliations:
1Otto-von-Guericke-Universität Magdeburg, External Organizations, ou_1738156              
2International Max Planck Research School (IMPRS), Max Planck Institute for Dynamics of Complex Technical Systems, Max Planck Society, ou_1738143              

Content

show
hide
Free keywords: -
 Abstract: In 1991, Yannakakis [17] proved that no symmetric extended formulation for the matching polytope of the complete graph K n with n nodes has a number of variables and constraints that is bounded subexponentially in n. Here, symmetric means that the formulation remains invariant under all permutations of the nodes of K n . It was also conjectured in [17] that “asymmetry does not help much,” but no corresponding result for general extended formulations has been found so far. In this paper we show that for the polytopes associated with the matchings in K n with logn edges there are non-symmetric extended formulations of polynomial size, while nevertheless no symmetric extended formulation of polynomial size exists. We furthermore prove similar statements for the polytopes associated with cycles of length logn . Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot. © Springer, Part of Springer Science+Business Media [accessed 2014 January 31st]

Details

show
hide
Language(s): eng - English
 Dates: 2010
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 569910
DOI: 10.1007/978-3-642-13036-6_11
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Integer Programming and Combinatorial Optimization
Source Genre: Book
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 135 - 148 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6080 Sequence Number: - Start / End Page: - Identifier: -