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

DOI10.1016/J.ORL.2012.01.010zbMATH Open1245.90101OpenAlexW2169764437WikidataQ57702158 ScholiaQ57702158MaRDI QIDQ439900FDOQ439900

Authors: Laura Galli, Konstantinos Kaparis, Adam N. Letchford 

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

Recommendations

• Gap inequalities for the max-cut problem: a cutting-plane algorithm
• Gap inequalities for the cut polytope
• On the separation of split cuts and related inequalities
• A note on the 2-circulant inequalities for the MAX-cut problem
• Gap inequalities for non-convex mixed-integer quadratic programs

zbMATH Keywords

computational complexitycutting planesmax-cut problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Gap inequalities for non-convex mixed-integer quadratic programs
• A guide to conic optimisation and its applications
• Discrete and Computational Geometry
• Gap inequalities for the max-cut problem: a cutting-plane algorithm
• A note on the 2-circulant inequalities for the MAX-cut problem

This page was built for publication: Complexity results for the gap inequalities for the max-cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439900)