Solving the max-cut problem using eigenvalues
From MaRDI portal
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
(22)- 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
- 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
- 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)
