A branch-and-bound algorithm for solving max-\(k\)-cut problem
From MaRDI portal
Publication:2231324
DOI10.1007/s10898-021-00999-zzbMath1478.90109OpenAlexW3131083459MaRDI QIDQ2231324
Publication date: 29 September 2021
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10898-021-00999-z
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Alternating direction augmented Lagrangian methods for semidefinite programming
- 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
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Optimization, approximation, and complexity classes
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Facets of the \(k\)-partition polytope
- Semidefinite programming relaxations for the graph partitioning problem
- Exploiting sparsity for the min \(k\)-partition problem
- Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
- The partition problem
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- A Coordinate Ascent Method for Solving Semidefinite Relaxations of Non-convex Quadratic Integer Programs
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method
This page was built for publication: A branch-and-bound algorithm for solving max-\(k\)-cut problem