On the cut polytope

DOI10.1007/BF02592023zbMath0616.90058OpenAlexW2012605254MaRDI QIDQ4726054

Francisco Barahona, Ali Ridha Mahjoub

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02592023

zbMATH Keywords

facet-defining inequalitiescut polytopepolyhedral combinatoricsadjacencyfacets of polyhedramax cut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Polytopes and polyhedra (52Bxx)

Cites Work

• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Matroids and multicommodity flows
• The ellipsoid method and its consequences in combinatorial optimization
• On the notion of balance of a signed graph
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• Facets of the Bipartite Subgraph Polytope
• Finding a Maximum Cut of a Planar Graph in Polynomial Time

Related Items (only showing first 100 items - show all)

The partition problem ⋮ A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems ⋮ On the optimality of the random hyperplane rounding technique for MAX CUT ⋮ The Boolean Quadric Polytope ⋮ Normal binary graph models ⋮ Gorenstein cut polytopes ⋮ Speeding up IP-based algorithms for constrained quadratic 0-1 optimization ⋮ On random 2-adjacent 0/1-polyhedra ⋮ The equipartition polytope. I: Formulations, dimension and basic facets ⋮ The equipartition polytope. II: Valid inequalities and facets ⋮ LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison ⋮ Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization ⋮ Necessary conditions for extended noncontextuality in general sets of random variables ⋮ Generalised 2-circulant inequalities for the max-cut problem ⋮ A note on the 2-circulant inequalities for the MAX-cut problem ⋮ Quantum Annealing versus Digital Computing ⋮ Trader multiflow and box-TDI systems in series-parallel graphs ⋮ The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints ⋮ On the bond polytope ⋮ A branch-and-cut algorithm for the connected max-\(k\)-cut problem ⋮ A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem ⋮ Binary Positive Semidefinite Matrices and Associated Integer Polytopes ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Faster exact solution of sparse maxcut and QUBO problems ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems ⋮ Crossing Minimization in Storyline Visualization ⋮ A polyhedral study of lifted multicuts ⋮ Generalized cut polytopes for binary hierarchical models ⋮ Cycle algebras and polytopes of matroids ⋮ The st-bond polytope on series-parallel graphs ⋮ Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches ⋮ Lower and upper bounds for the linear arrangement problem on interval graphs ⋮ The Multilinear Polytope for Acyclic Hypergraphs ⋮ Generating facets for the cut polytope of a graph by triangular elimination ⋮ Facet-defining inequalities for the simple graph partitioning polytope ⋮ Transitive packing ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem ⋮ Improving spectral bounds for clustering problems by Lagrangian relaxation ⋮ On the Matrix-Cut Rank of Polyhedra ⋮ The cut cone. III: On the role of triangle facets ⋮ A Lagrangian relaxation approach to the edge-weighted clique problem ⋮ The QAP-polytope and the star transformation ⋮ Exploring the relationship between max-cut and stable set relaxations ⋮ The cut cone. III: On the role of triangle facets ⋮ Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES ⋮ New quadratic models for the maximum weighted cut problem ⋮ Computing cyclic invariants for molecular graphs ⋮ A semidefinite programming based polyhedral cut and price approach for the maxcut problem ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Max cut and semidefinite rank ⋮ Computational Approaches to Max-Cut ⋮ Global Approaches for Facility Layout and VLSI Floorplanning ⋮ On skeletons, diameters and volumes of metric polyhedra ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ On the dominant of the multicut polytope ⋮ Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization ⋮ Spectral bounds for the maximum cut problem ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ Sherali-adams strikes back ⋮ Enumeration of the facets of cut polytopes over some highly symmetric graphs ⋮ On fractional cut covers ⋮ A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching ⋮ Generalized network design polyhedra ⋮ Unnamed Item ⋮ A note on the Boolean quadric polytope ⋮ Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint ⋮ Cuts for mixed 0-1 conic programming ⋮ Unnamed Item ⋮ A new separation algorithm for the Boolean quadric and cut polytopes ⋮ New approaches for optimizing over the semimetric polytope ⋮ Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut ⋮ Tight Cycle Relaxations for the Cut Polytope ⋮ On the diameter of cut polytopes ⋮ Mixed integer formulations using natural variables for single machine scheduling around a common due date ⋮ Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods ⋮ Decomposition and optimization over cycles in binary matroids ⋮ On the magnetisation of the ground states in two dimensional Ising spin glasses ⋮ Application of cut polyhedra. I ⋮ Applications of cut polyhedra. II ⋮ The expected relative error of the polyhedral approximation of the max- cut problem ⋮ A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope ⋮ On a positive semidefinite relaxation of the cut polytope ⋮ Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors ⋮ Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems ⋮ Facets of the \(k\)-partition polytope ⋮ Improved compact formulations for metric and cut polyhedra ⋮ An extended edge-representative formulation for the \(K\)-partitioning problem ⋮ Some new classes of facets for the equicut polytope ⋮ Solving the max-cut problem using eigenvalues ⋮ Stochastic graph partitioning: quadratic versus SOCP formulations ⋮ Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables ⋮ Improved exact approaches for row layout problems with departments of equal length ⋮ A polynomial characterization of some graph partitioning problems ⋮ Semidefinite programming in combinatorial optimization ⋮ Cuts, matrix completions and graph rigidity ⋮ On decomposability of multilinear sets

This page was built for publication: On the cut polytope