THE EQUIPARTITION POLYTOPE .2. VALID INEQUALITIES AND FACETS

被引：24

作者：

CONFORTI, M ^{[1
]}

RAO, MR ^{[1
]}

SASSANO, A ^{[1
]}

机构：

[1] CNR,IST ANAL SISTEMI & INFORMAT,I-00185 ROME,ITALY

来源：

MATHEMATICAL PROGRAMMING | 1990年 / 49卷 / 01期

关键词：

Boolean quadratic programming; cut polytope; Equipartition polytope;

D O I：

10.1007/BF01588779

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The equipartition problem is defined as follows: given a graph G = (V, E) and edge weights ce, partition the set V into two sets of ⌈1/2|V|⌉ and ⌊1/2|V|⌋ nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized. An equicut is a feasible solution of the above problem and the equicut polytope Q(G) is the convex hull of the incidence vectors of equicuts in G. In this paper we describe some facet inducing inequalities of this polytope. © 1990 The Mathematical Programming Society, Inc.

引用

页码：71 / 90

页数：20