Computational approaches to MAX-cut
DOI10.1007/978-1-4614-0769-0_28zbMATH Open1334.90149OpenAlexW68231821MaRDI QIDQ2802547FDOQ2802547
Authors: L. Palagi, Veronica Piccialli, Franz Rendl, G. Rinaldi, Angelika Wiegele 
Publication date: 26 April 2016
Published in: International Series in Operations Research & Management Science (Search for Journal in Brave)
Full work available at URL: http://www.springer.com/business+%26+management/operations+research/book/978-1-4614-0768-3
Recommendations
Combinatorial optimization (90C27) Semidefinite programming (90C22) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01)
Cites Work
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
- An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Trust-region methods on Riemannian manifolds
- Benchmarking optimization software with performance profiles.
- A Spectral Bundle Method for Semidefinite Programming
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Multiplier and gradient methods
- Title not available (Why is that?)
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- Geometry of cuts and metrics
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- On the cut polytope
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Problems of distance geometry and convex properties of quadratic maps
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Title not available (Why is that?)
- Extremal correlation matrices
- Semidefinite relaxations of ordering problems
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Nonmonotone globalization techniques for the Barzilai-Borwein gradient method
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- Semidefinite programming and integer programming
- Facets of the linear ordering polytope
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Exact algorithms for the quadratic linear ordering problem
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- Title not available (Why is that?)
- Low-rank optimization on the cone of positive semidefinite matrices
- Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
Cited In (15)
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- Recognizing max-flow min-cut path matrices
- Advanced scatter search for the max-cut problem
- \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM
- Title not available (Why is that?)
- The maximum cut problem
- Canonical dual approach to solving the maximum cut problem
- Generalised 2-circulant inequalities for the max-cut problem
- Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Towards Algorithmic Cut-Introduction
- Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
- A MAX-CUT formulation of 0/1 programs
- Quadratic Combinatorial Optimization Using Separable Underestimators
- A note on the 2-circulant inequalities for the MAX-cut problem
Uses Software
This page was built for publication: Computational approaches to MAX-cut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802547)
