Complexity results for the gap inequalities for the max-cut problem
type: Item
instance of: scholarly article
title: Complexity results for the gap inequalities for the max-cut problem
zbMATH Open document ID: 1245.90101
author: Laura Galli
author: Konstantinos Kaparis
author: Adam N. Letchford
published in: Operations Research Letters
publication date: 2012-08-17T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6067684
zbMATH Keywords: computational complexity
zbMATH Keywords: max-cut problem
zbMATH Keywords: cutting planes
MaRDI profile type: Publication
Wikidata QID: Q57702158
full work available at URL: j.orl.2012.01.010
OpenAlex ID: W2169764437
cites work: Discrete and Computational Geometry
cites work: A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
cites work: Stronger linear programming relaxations of max-cut
cites work: On the cut polytope
cites work: Q3241581
cites work: Fifty-Plus Years of Combinatorial Integer Programming
cites work: The hypermetric cone is polyhedral
cites work: Geometry of cuts and metrics
cites work: Gap inequalities for non-convex mixed-integer quadratic programs
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Exploring the relationship between max-cut and stable set relaxations
cites work: Geometric algorithms and combinatorial optimization
cites work: Q4142699
cites work: Q4089444
cites work: Q4398372
cites work: On the Facial Structure of the Set of Correlation Matrices
cites work: On a positive semidefinite relaxation of the cut polytope
cites work: Binary positive semidefinite matrices and associated integer polytopes
cites work: Metric Spaces and Positive Definite Functions
cites work: The Simplex Method for Quadratic Programming
DOI: 10.1016/J.ORL.2012.01.010
description: scientific article; zbMATH DE number 6067684