• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Facets for the cut cone I

Thumbnail
View/Open
6460305.pdf (1.853Mb)
Date
1992
Dewey
Probabilités et mathématiques appliquées
Sujet
Max-cut problem; cone; polytope; facet; lifting; hypermetric inequality
Journal issue
Mathematical Programming
Volume
56
Number
1-3
Publication date
1992
Article pages
121-160
Publisher
Springer
DOI
http://dx.doi.org/10.1007/BF01580897
URI
https://basepub.dauphine.fr/handle/123456789/14446
Collections
  • CEREMADE : Publications
Metadata
Show full item record
Author
Deza, Michel
Laurent, Monique
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.