Collapsing and lifting for the cut cone

DOI10.1016/0012-365X(92)00471-3zbMath0799.90099MaRDI QIDQ1322220

Caterina De Simone, Monique Laurent, Michel Marie Deza

Publication date: 5 May 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

cut polytopecollapsing an inequalityinequalities defining facets

Mathematics Subject Classification ID

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

Related Items

Application of cut polyhedra. I, New classes of facets of the cut polytope and tightness of \(I_{mm22}\) Bell inequalities, Facets of the \(k\)-partition polytope, Generalised 2-circulant inequalities for the max-cut problem, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, The Hypermetric Cone on Seven Vertices, Facets for the cut cone. II: Clique-web inequalities, The cut cone. III: On the role of triangle facets, The cut cone. III: On the role of triangle facets

Cites Work

• Sur les inégalités valides dans \(L^ 1\)
• Lifting facets of the cut polytope
• The classification of finite connected hypermetric spaces
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• All the facets of the six-point Hamming cone
• All facets of the cut cone \(C_ n\) for \(n=7\) are known
• Path Partitions in Directed Graphs
• Hypermetric Spaces and the Hamming Cone
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Clique-Web Facets for Multicut Polytopes
• On the cut polytope
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item