Generalised 2-circulant inequalities for the max-cut problem

DOI10.1016/j.orl.2022.01.005OpenAlexW4206705411MaRDI QIDQ2670485

Konstantinos Kaparis, Adam N. Letchford, Ioannis Mourtos

Publication date: 11 March 2022

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

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

zbMATH Keywords

cutting planesmax-cut problempolyhedral combinatorics

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Uses Software

• Biq Mac

Cites Work

• Unnamed Item
• Lifting and separation procedures for the cut polytope
• Sur les inégalités valides dans \(L^ 1\)
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Experiments in quadratic 0-1 programming
• Facets for the cut cone. I
• Max-cut in circulant graphs
• Some simplified NP-complete graph problems
• Collapsing and lifting for the cut cone
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• On a positive semidefinite relaxation of the cut polytope
• Gap inequalities for the cut polytope
• A new separation algorithm for the Boolean quadric and cut polytopes
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A note on the 2-circulant inequalities for the MAX-cut problem
• Computational Approaches to Max-Cut
• Integer Programming
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• On the cut polytope
• Fibonacci heaps and their uses in improved network optimization algorithms
• Geometry of cuts and metrics
• On disjunctive cuts for combinatorial optimization