Solving the max-cut problem using eigenvalues

DOI10.1016/0166-218X(94)00155-7MaRDI QIDQ1900149zbMATH OpenFDO

Authors Svatopluk Poljak, Franz Rendl

Publication date 30 May 1996

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

Full work available at URL https://doi.org/10.1016/0166-218X(94)00155-7

zbMATH Keywords

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Node and edge relaxations of the max-cut problem

Cites work

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

Cited in

(24)

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

This page was built for publication: Solving the max-cut problem using eigenvalues

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