Facets for the cut cone I

Facets for the cut cone I

0.00 Avg rating0 Votes
Article ID: iaor1993658
Country: Netherlands
Volume: 56
Issue: 2
Start Page Number: 121
End Page Number: 160
Publication Date: Sep 1992
Journal: Mathematical Programming
Authors: ,
Abstract:

The authors study facets of the cut cone equ1i.e., the cone of dimension equ2generated by the cuts of the complete graph on n 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. The authors present several operations on facets and, in particular, a ‘lifting’ procedure for constructing facets of equ3from given facets of lower dimensional cone equ4. After reviewing hypermetric valid inequalities, they 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.

Reviews

Required fields are marked *. Your email address will not be published.