• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • Consulter le document
  •   Accueil
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail

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
6460305.pdf (1.853Mb)
Type
Article accepté pour publication ou publié
Date
1992
Nom de la revue
Mathematical Programming
Volume
56
Numéro
1-3
Éditeur
Springer
Pages
121-160
Identifiant publication
http://dx.doi.org/10.1007/BF01580897
Métadonnées
Afficher la notice complète
Auteur(s)
Deza, Michel
Laurent, Monique
Ré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 inequality

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Facets for the cut cone II: Clique-web inequalities 
    Deza, Michel; Laurent, Monique (1992) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    The cut cone III: On the role of triangle facets 
    Deza, Michel; Laurent, Monique; Poljak, Svatopluk (1992) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Bouquets of geometric lattices: some algebraic and topological aspects 
    Laurent, Monique; Deza, Michel (1989) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Bouquets of Geometric Lattices: some Algebraic and Topological Aspects 
    Laurent, Monique; Deza, Michel (1989) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    A characterization of knapsacks with the max-flow-—min-cut property 
    Laurent, Monique; Sassano, Antonio (1992) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo