Solving the max-cut problem using eigenvalues

DOI10.1016/0166-218X(94)00155-7zbMath0838.90131MaRDI QIDQ1900149

Svatopluk Poljak, Franz Rendl

Publication date: 30 May 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational experimentsbranch-and-boundmax-cut problemeigenvalue relaxationquadratic 0-1 optimizationsubdifferential optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

The expected relative error of the polyhedral approximation of the max- cut problem, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, A projection technique for partitioning the nodes of a graph, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, SDP-based branch-and-bound for non-convex quadratic integer optimization, A new global algorithm for max-cut problem with chordal sparsity, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, On Laplacian spectra of parametric families of closely connected networks with application to cooperative control, Simplicial faces of the set of correlation matrices, Maximum cut in fuzzy nature: models and algorithms, Semidefinite programming and combinatorial optimization, A multiple penalty function method for solving max-bisection problems, Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs, Spectral partitioning with multiple eigenvectors, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT, A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem, Laplacian eigenvalues and the maximum cut problem, Node and edge relaxations of the max-cut problem

Cites Work

• Combinatorial properties and the complexity of a max-cut approximation
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• On cuts and matchings in planar graphs
• Solution of large-scale symmetric travelling salesman problems
• How easy is local search?
• Experiments in quadratic 0-1 programming
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• Laplacian eigenvalues and the maximum cut problem
• Node and edge relaxations of the max-cut problem
• A projection technique for partitioning the nodes of a graph
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• A Dynamic Programming Approach to Sequencing Problems
• Matrix Analysis
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• An Efficient Heuristic Procedure for Partitioning Graphs
• Eigenvalue perturbations and nonlinear parametric optimization
• On the cut polytope
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• A man-machine approach toward solving the traveling salesman problem
• Lower Bounds for the Partitioning of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item