Spectral bounds for the maximum cut problem

DOI10.1002/NET.20220MaRDI QIDQ3632965zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A class of spectral bounds for max \(k\)-cut
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• scientific article; zbMATH DE number 780784
• Combinatorial properties and the complexity of a max-cut approximation
• scientific article; zbMATH DE number 426360

Cites work

• 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 4193718 (Why is no real title available?)
• scientific article; zbMATH DE number 2196287 (Why is no real title available?)
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Bipartite Subgraphs and the Smallest Eigenvalue
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial properties and the complexity of a max-cut approximation
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Geometry of cuts and metrics
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Laplacian eigenvalues and the maximum cut problem
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• On the cut polytope
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Semidefinite optimization
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Stronger linear programming relaxations of max-cut
• The expected relative error of the polyhedral approximation of the max- cut problem
• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• Using domain decomposition to find graph bisectors

Cited in

(14)

• On spectral bounds for cutsets
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Tighter spectral bounds for the cut size, based on Laplacian eigenvectors
• Spectral bounds for graph partitioning with prescribed partition sizes
• Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
• A class of spectral bounds for max \(k\)-cut
• Laplacian eigenvalues and the maximum cut problem
• scientific article; zbMATH DE number 426360 (Why is no real title available?)
• From Graph Orientation to the Unweighted Maximum Cut
• Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems
• Improved estimation of duality gap in binary quadratic programming using a weighted distance measure
• On duality gap in binary quadratic programming
• New bounds for the maximum cut problem
• Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning

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

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