Show simple item record

dc.contributor.authorDeza, Michel
dc.contributor.authorLaurent, Monique
dc.date.accessioned2014-12-15T09:40:09Z
dc.date.available2014-12-15T09:40:09Z
dc.date.issued1992
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14446
dc.language.isoenen
dc.subjectMax-cut problemen
dc.subjectconeen
dc.subjectpolytopeen
dc.subjectfaceten
dc.subjectliftingen
dc.subjecthypermetric inequalityen
dc.subject.ddc519en
dc.titleFacets for the cut cone Ien
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameMathematical Programming
dc.relation.isversionofjnlvol56en
dc.relation.isversionofjnlissue1-3en
dc.relation.isversionofjnldate1992
dc.relation.isversionofjnlpages121-160en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/BF01580897en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record