Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Symmetry Matters for the Sizes of Extended Formulations
verfasst von : Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\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.