Nonpolyhedral Relaxations of Graph-Bisection Problems

DOI10.1137/0805024zbMATH Open0838.90130OpenAlexW2085595139MaRDI QIDQ4852576FDOQ4852576

Authors: Svatopluk Poljak, Franz Rendl 

Publication date: 1 November 1995

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/aeb498e247313d45cc70a5c43e9af9c7c130bdad

Recommendations

• scientific article; zbMATH DE number 5237020
• Graph bisection revisited
• Node and edge relaxations of the max-cut problem
• Better Bounds for Graph Bisection
• On the Graph Bisection Cut Polytope

zbMATH Keywords

minimum bisectionmax-cut problemgraph bisectionpositive semidefinite relaxations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Semi-infinite programming (90C34)

Cited In (31)

• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• Spectral bounds for the maximum cut problem
• Mathematical programming models and exact algorithms
• Gap inequalities for non-convex mixed-integer quadratic programs
• Using the eigenvalue relaxation for binary least-squares estimation problems
• Spectral methods for graph bisection problems.
• Solving the max-cut problem using eigenvalues
• A projection technique for partitioning the nodes of a graph
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Heuristics for semirandom graph problems
• A guide to conic optimisation and its applications
• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
• Title not available (Why is that?)
• Semidefinite programming in combinatorial optimization
• Applications of cut polyhedra. II
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• The real positive semidefinite completion problem for series-parallel graphs
• Rank optimality for the Burer-Monteiro factorization
• Semidefinite programming and combinatorial optimization
• Node and edge relaxations of the max-cut problem
• On semidefinite programming relaxations of maximum \(k\)-section
• Cardinality constrained minimum cut problems: complexity and algorithms.
• On the Graph Bisection Cut Polytope
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• On the facets of the lift-and-project relaxations of graph subdivisions
• The solution of Euclidean norm trust region SQP subproblems via second-order cone programs: an overview and elementary introduction
• On a positive semidefinite relaxation of the cut polytope
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems
• The Boolean quadric polytope
• Title not available (Why is that?)

This page was built for publication: Nonpolyhedral Relaxations of Graph-Bisection Problems

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