# zbMATH — the first resource for mathematics

Facets for the cut cone. I. (English) Zbl 0768.90074
Summary: We study facets of the cut cone $$C_ n$$, i.e., the cone of dimension $${1\over 2} n(n-1)$$ generated 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. We present several operations on facets and, in particular, a “lifting” procedure for constructing facets of $$C_{n+1}$$ from given facets of the lower dimensional cone $$C_ 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.
[For part II see the authors, ibid. 56A, No. 2, 161-188 (1992; Zbl 0768.90075)].

##### MSC:
 90C35 Programming involving graphs or networks 90C27 Combinatorial optimization 52B12 Special polytopes (linear programming, centrally symmetric, etc.)
Full Text: