• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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

View/Open
6460305.pdf (1.853Mb)
Type
Article accepté pour publication ou publié
Date
1992
Journal name
Mathematical Programming
Volume
56
Number
1-3
Publisher
Springer
Pages
121-160
Publication identifier
http://dx.doi.org/10.1007/BF01580897
Metadata
Show full item record
Author(s)
Deza, Michel
Laurent, Monique
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 / Keywords
Max-cut problem; cone; polytope; facet; lifting; hypermetric inequality

Related items

Showing items related by title and author.

  • Thumbnail
    Facets for the cut cone II: Clique-web inequalities 
    Deza, Michel; Laurent, Monique (1992) Article accepté pour publication ou publié
  • Thumbnail
    The cut cone III: On the role of triangle facets 
    Deza, Michel; Laurent, Monique; Poljak, Svatopluk (1992) Article accepté pour publication ou publié
  • Thumbnail
    Bouquets of geometric lattices: some algebraic and topological aspects 
    Laurent, Monique; Deza, Michel (1989) Article accepté pour publication ou publié
  • Thumbnail
    Bouquets of Geometric Lattices: some Algebraic and Topological Aspects 
    Laurent, Monique; Deza, Michel (1989) Article accepté pour publication ou publié
  • Thumbnail
    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
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo