FACETS FOR THE CUT CONE .2. CLIQUE-WEB INEQUALITIES

被引：23

作者：

DEZA, M ^{[1
]}

LAURENT, M ^{[1
]}

机构：

[1] UNIV PARIS 09,LAMSADE,CNRS,F-75576 PARIS 16,FRANCE

来源：

MATHEMATICAL PROGRAMMING | 1992年 / 56卷 / 02期

关键词：

CONE; POLYTOPE; FACET; ANTIWEB; CUT; HYPERMETRIC INEQUALITY;

D O I：

10.1007/BF01580898

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 [计算机软件与理论]; 0835 [软件工程];

摘要：

We study new classes of facets for the cut cone C(n) generated by the cuts of the complete graph on n vertices. This cone can also be interpreted as the cone of all semi-metrics on n points that are isometrically l1-embeddable and, in fact, the study of the facets of the cut polytope is in some sense equivalent to the study of the facets of C(n). These new facets belong to the class of clique-web inequalities which generalize the hypermetric and cycle inequalities as well as the bicycle odd wheel inequalities.

引用

页码：161 / 188

页数：28

共 19 条

[1]

ALON N, 1990, EUR J COMBIN, V11, P1

[2]

ASSOUAD P, 1982, PUBLICATIONS MATH OR, V3

[3]

ASSOUAD P, 1980, ANN DISCRETE MATH, V8, P197

[4]

THE CUT CONE, L1 EMBEDDABILITY, COMPLEXITY, AND MULTICOMMODITY FLOWS [J].