Tight Cycle Relaxations for the Cut Polytope

DOI10.1137/20M1318523zbMath1483.90142OpenAlexW4205305404MaRDI QIDQ5020841

Carla Michini

Publication date: 7 January 2022

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

Full work available at URL: https://doi.org/10.1137/20m1318523

zbMATH Keywords

cut polytopesigned graphmetric polytopeBoolean quadric polytopeodd minorcycle relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (2)

Efficient joint object matching via linear programming ⋮ On the complexity of binary polynomial optimization over acyclic hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• The ellipsoid method and its consequences in combinatorial optimization
• The matroids with the max-flow min-cut property
• Easy and difficult objective functions for max cut
• The cut polytope and the Boolean quadric polytope
• A characterization of weakly bipartite graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial Optimization
• L’algebre de Boole et ses applications en recherche operationnelle
• Methods of Nonlinear 0-1 Programming
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• Dominants and submissives of matching polyhedra
• On the cut polytope
• Reducibility among Combinatorial Problems
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• The Graph Minor Algorithm with Parity Conditions
• Geometry of cuts and metrics
• Optimization via enumeration: A new algorithm for the max cut problem

This page was built for publication: Tight Cycle Relaxations for the Cut Polytope