Solving the max-cut problem using eigenvalues

DOI10.1016/0166-218X(94)00155-7zbMATH Open0838.90131MaRDI QIDQ1900149FDOQ1900149

Svatopluk Poljak, Franz Rendl

Publication date: 30 May 1996

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

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

Cited In (21)

• Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
• A projection technique for partitioning the nodes of a graph
• Combinatorial properties and the complexity of a max-cut approximation
• Simplicial faces of the set of correlation matrices
• Spectral partitioning with multiple eigenvectors
• Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
• New bounds for the \(\max\)-\(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
• 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
• SDP-based branch-and-bound for non-convex quadratic integer optimization
• On Laplacian spectra of parametric families of closely connected networks with application to cooperative control
• 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)