Kaibel, Volker; Pashkovich, Kanstantsin; Theis, Dirk Oliver Symmetry matters for the sizes of extended formulations. (English) Zbl 1285.90052 Eisenbrand, Friedrich (ed.) et al., Integer programming and combinatorial optimization. 14th international conference, IPCO 2010, Lausanne, Switzerland, June 9–11, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13035-9/pbk). Lecture Notes in Computer Science 6080, 135-148 (2010). Summary: In [J. Comput. Syst. Sci. 43, No. 3, 441–466 (1991; Zbl 0748.90074)], M. Yannakakis 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 [loc. cit.] 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 \(\lfloor\log n\rfloor\) 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 \(\lfloor\log n\rfloor\). Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot.For the entire collection see [Zbl 1189.90006]. Cited in 11 Documents MSC: 90C27 Combinatorial optimization 05C38 Paths and cycles 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Citations:Zbl 0748.90074 PDFBibTeX XMLCite \textit{V. Kaibel} et al., Lect. Notes Comput. Sci. 6080, 135--148 (2010; Zbl 1285.90052) Full Text: DOI arXiv