Otto-von-Guericke-Universität Magdeburg

 
 
 
 
 
 
 
 

11-24

by Kaibel, V.; Pashkovich, K.; Theis, D. O.

 

Preprint series: 11-24, Preprints

MSC:
90C10 Integer programming
ZDM:
52B12

 

Abstract: In 1991, Yannakakis [17] proved that no symmetric extended formulation for the matching polytope of the complete graph Kn 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 Kn. 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 Kn with blog nc edges there are non-symmetric extended formulations of polynomial size, while nevertheless no symmetric extended formulations of polynomial size exist. We furthermore prove similar statements for the polytopes associated with cycles of length blog nc. Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot. Compared to the extended abtract [12], this paper does not only contain proofs that had been ommitted there, but it also presents slightly generalized and sharpened lower bounds.

Keywords: polytope, projection, matching, cycle


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 10.02.2016 - Ansprechpartner: Pierre Krenzlin