
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
Voir/Ouvrir
Type
Article accepté pour publication ou publiéDate
1992Nom de la revue
Mathematical ProgrammingVolume
56Numéro
1-3Éditeur
Springer
Pages
121-160
Identifiant publication
Métadonnées
Afficher la notice complèteRésumé (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.Mots-clés
Max-cut problem; cone; polytope; facet; lifting; hypermetric inequalityPublications associées
Affichage des éléments liés par titre et auteur.
-
Deza, Michel; Laurent, Monique (1992) Article accepté pour publication ou publié
-
Deza, Michel; Laurent, Monique; Poljak, Svatopluk (1992) Article accepté pour publication ou publié
-
Laurent, Monique; Deza, Michel (1989) Article accepté pour publication ou publié
-
Laurent, Monique; Deza, Michel (1989) Article accepté pour publication ou publié
-
Laurent, Monique; Sassano, Antonio (1992) Article accepté pour publication ou publié