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

DOI10.1016/J.ORL.2012.01.010MaRDI QIDQ439900zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

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

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)