Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Buchkapitel

Symmetry Matters for Sizes of Extended Formulations

MPG-Autoren
/persons/resource/persons125782

Pashkovich,  Kanstantsin
International Max Planck Research School (IMPRS), Max Planck Institute for Dynamics of Complex Technical Systems, Max Planck Society;
Otto-von-Guericke-Universität Magdeburg, External Organizations;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-002E-A38F-A
Zusammenfassung
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]