Spectral bounds for the maximum cut problem

DOI10.1002/net.20220zbMath1170.90462OpenAlexW4231459855MaRDI QIDQ3632965

Walid Ben-Ameur, José Neto

Publication date: 16 June 2009

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20220

zbMATH Keywords

eigenvaluesrelaxations

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (6)

A class of spectral bounds for max \(k\)-cut ⋮ Improved estimation of duality gap in binary quadratic programming using a weighted distance measure ⋮ On duality gap in binary quadratic programming ⋮ Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ Spectral bounds for graph partitioning with prescribed partition sizes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial properties and the complexity of a max-cut approximation
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• Laplacian eigenvalues and the maximum cut problem
• Using domain decomposition to find graph bisectors
• Stronger linear programming relaxations of max-cut
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The expected relative error of the polyhedral approximation of the max- cut problem
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure
• Semidefinite optimization
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the optimality of the random hyperplane rounding technique for MAX CUT
• On the cut polytope
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Bipartite Subgraphs and the Smallest Eigenvalue
• Geometry of cuts and metrics

This page was built for publication: Spectral bounds for the maximum cut problem