A branch-and-bound algorithm for solving max-\(k\)-cut problem

DOI10.1007/s10898-021-00999-zzbMath1478.90109OpenAlexW3131083459MaRDI QIDQ2231324

Cheng Lu, Zhi-bin Deng

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

zbMATH Keywords

branch-and-bound algorithmsemidefinite relaxationmax-\(k\)-cut

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (1)

A semidefinite relaxation based global algorithm for two-level graph partition problem

Uses Software

• Biq Mac

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