Symmetry Matters for the Sizes of Extended Formulations
Symmetry Matters for the Sizes of Extended Formulations
复制标题
对称性对于扩展配方的尺寸很重要
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Theis
中科院分区：
文献类型：
--
作者：
V. Kaibel;Kanstantsin Pashkovich;D. Theis
1991年，Yannakakis [17]证明了具有n个节点的完全图Kn的匹配多面体的对称扩展公式不具有在n中次指数有界的多个变量和约束。这里，对称意味着公式在Kn的节点的所有排列下保持不变。在[17]中也指出了“不对称性没有多大帮助”，但到目前为止还没有发现一般扩展公式的相应结果。在本文中，我们证明了，对于与Kn中的匹配相关联的多面体，
存在多项式大小的非对称扩展公式，然而不存在多项式大小的对称扩展公式。我们还证明了类似的声明与周期长度为$lfloorlog n的多面体
地板$因此，关于最小可能的扩展公式的问题，一般来说，对称性要求可能很重要。
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 $lfloorlog n
floor$ 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 $lfloorlog n
floor$. Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot.