Facets for the cut cone I
Deza, Michel; Laurent, Monique (1992), Facets for the cut cone I, Mathematical Programming, 56, 1-3, p. 121-160. http://dx.doi.org/10.1007/BF01580897
TypeArticle accepté pour publication ou publié
Journal nameMathematical Programming
MetadataShow full item record
Abstract (EN)We study facets of the cut coneC n , i.e., the cone of dimension 1/2n(n − 1) generated by the cuts of the complete graph onn vertices. Actually, the study of the facets of the cut cone is equivalent in some sense to the study of the facets of the cut polytope. We present several operations on facets and, in particular, a “lifting” procedure for constructing facets ofC n+1 from given facets of the lower dimensional coneC n . After reviewing hypermetric valid inequalities, we describe the new class of cycle inequalities and prove the facet property for several subclasses. The new class of parachute facets is developed and other known facets and valid inequalities are presented.
Subjects / KeywordsMax-cut problem; cone; polytope; facet; lifting; hypermetric inequality
Showing items related by title and author.