Complexity results for the gap inequalities for the max-cut problem

DOI10.1016/j.orl.2012.01.010zbMath1245.90101OpenAlexW2169764437WikidataQ57702158 ScholiaQ57702158MaRDI QIDQ439900

Laura Galli, Adam N. Letchford, Konstantinos Kaparis

Publication date: 17 August 2012

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2012.01.010

zbMATH Keywords

computational complexitycutting planesmax-cut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

A guide to conic optimisation and its applications

Cites Work

• Gap inequalities for non-convex mixed-integer quadratic programs
• Binary positive semidefinite matrices and associated integer polytopes
• Geometric algorithms and combinatorial optimization
• Some simplified NP-complete graph problems
• The hypermetric cone is polyhedral
• Stronger linear programming relaxations of max-cut
• A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
• On a positive semidefinite relaxation of the cut polytope
• Exploring the relationship between max-cut and stable set relaxations
• The Simplex Method for Quadratic Programming
• Fifty-Plus Years of Combinatorial Integer Programming
• On the cut polytope
• On the Facial Structure of the Set of Correlation Matrices
• Metric Spaces and Positive Definite Functions
• Discrete and Computational Geometry
• Geometry of cuts and metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item