Thumbnail

Facets for the cut cone II: Clique-web inequalities

Deza, Michel; Laurent, Monique (1992), Facets for the cut cone II: Clique-web inequalities, Mathematical Programming, 56, 1-3, p. 161-188. http://dx.doi.org/10.1007/BF01580898

View/Open
Type
Article accepté pour publication ou publié
Date
1992
Journal name
Mathematical Programming
Volume
56
Number
1-3
Publisher
Springer
Pages
161-188
Publication identifier
Metadata
Show full item record
Author(s)
Deza, Michel
Laurent, Monique
Abstract (EN)
We study new classes of facets for the cut coneC n generated by the cuts of the complete graph onn vertices. This cone can also be interpreted as the cone of all semi-metrics onn points that are isometricallyl 1-embeddable and, in fact, the study of the facets of the cut polytope is in some sense equivalent to the study of the facets ofC 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.
Subjects / Keywords
cone; polytope; facet; antiweb; cut; hypermetric inequality