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

DOI10.3934/jimo.2022250OpenAlexW4312440068MaRDI QIDQ2698612

Shaoze Li, Cheng Lu, Junhao Wu, Zhi-bin Deng

Publication date: 24 April 2023

Published in: Journal of Industrial and Management Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3934/jimo.2022250

zbMATH Keywords

branch-and-boundsemidefinite relaxationgraph partition

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20)

Uses Software

• Biq Mac

Cites Work

• Unnamed Item
• Stabilizer-based symmetry breaking constraints for mathematical programs
• Orbital branching
• A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
• Reformulations in mathematical programming: automatic symmetry detection and exploitation
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• 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
• A two-level graph partitioning problem arising in mobile wireless communications
• 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
• A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
• A branch-and-bound algorithm for solving max-\(k\)-cut problem
• Modified orbital branching for structured symmetry with an application to unit commitment
• The partition problem
• An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
• Symmetry in Integer Linear Programming
• Fundamental Domains for Integer Programs with Symmetries
• 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