Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
复制标题
割多面体、布尔二次多面体和非负二次伪布尔函数
DOI：
--
复制
发表时间：
1993
影响因子：
1.7
通讯作者：
P. Hammer
中科院分区：
文献类型：
--
作者：
E. Boros;P. Hammer
在本文中，我们介绍了一类有效的不平等以及完整图的切割物的一类。对于此类。相应的分离问题在多项式上是可解决的。 n变量。
In this paper we present a class of valid inequalities as well as a class of facets for the cut-polytope of the complete graph. It is shown that many of the known classes of valid inequalities, e.g., triangle, hypermetric and cycle inequalities, belong to this class. By specializing some of the parameters, large classes of facets can be defined. It is shown that each of these classes contains at least n/3n/3 facets, where n ⥠10 denotes the number of vertices, and that the corresponding separation problems are polynomially solvable. These results are based on a one-to-one correspondence established between the set of valid inequalities facets for the cut-polytope of Kn+1, and the set of nonnegative extremal quadratic pseudo-Boolean functions in n variables.