Computational Approaches to Max-Cut
From MaRDI portal
Publication:2802547
DOI10.1007/978-1-4614-0769-0_28zbMath1334.90149OpenAlexW68231821MaRDI QIDQ2802547
Giovanni Rinaldi, Laura Palagi, Angelika Wiegele, Veronica Piccialli, Franz Rendl
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
Semidefinite programming (90C22) Combinatorial optimization (90C27) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01)
Related Items
Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ Generalised 2-circulant inequalities for the max-cut problem ⋮ A note on the 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 ⋮ Improved semidefinite bounding procedure for solving max-cut problems to optimality ⋮ Quadratic Combinatorial Optimization Using Separable Underestimators ⋮ \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM ⋮ A MAX-CUT formulation of 0/1 programs ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Semidefinite relaxations of ordering problems
- An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Extremal correlation matrices
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Problems of distance geometry and convex properties of quadratic maps
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Nonmonotone globalization techniques for the Barzilai-Borwein gradient method
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
- Trust-region methods on Riemannian manifolds
- Multiplier and gradient methods
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- Exact Algorithms for the Quadratic Linear Ordering Problem
- Low-Rank Optimization on the Cone of Positive Semidefinite Matrices
- Facets of the linear ordering polytope
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A Spectral Bundle Method for Semidefinite Programming
- On the cut polytope
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- Geometry of cuts and metrics
- Benchmarking optimization software with performance profiles.
