CHVATAL CUTS AND ODD CYCLE INEQUALITIES IN QUADRATIC 0 - 1 OPTIMIZATION
CHVATAL CUTS AND ODD CYCLE INEQUALITIES IN QUADRATIC 0 - 1 OPTIMIZATION
复制标题
DOI：
10.1137/0405014
复制
发表时间：
1992-05-01
影响因子：
0.8
通讯作者：
HAMMER, PL
中科院分区：
文献类型：
--
作者：
BOROS, E;CRAMA, Y;HAMMER, PL
本文研究了无约束二次 0-1 最小化的新下界。 结果表明，这个界限可以通过求解变量数量为多项式大小的线性规划问题来计算；结果表明，由该 LP 公式的约束定义的多面体 S[3] 正是与标准线性化过程相关的多面体的第一个 Chvatal 闭包。 通过将二次极小化问题重写为带权符号图中的平衡问题，可以看出奇循环不等式定义的多面体在某种意义上与S[3]是等价的。 作为推论，针对弱二分图情况的最大割问题，提出了紧凑的线性规划公式。
In this paper a new lower bound for unconstrained quadratic 0-1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the number of variables; and it is shown that the polyhedron S[3], defined by the constraints of this LP formulation is precisely the first Chvatal closure of the polyhedron associated with standard linearization procedures. By rewriting the quadratic minimization problem as a balancing problem in a weighted signed graph, it can be seen that the polyhedron defined by the odd cycle inequalities is equivalent, in a certain sense, with S[3]. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs.