SDP-based bounds for graph partition via extended ADMM

DOI10.1007/s10589-022-00355-1zbMath1490.90259arXiv2105.09075OpenAlexW4221034559MaRDI QIDQ2125076

Shudian Zhao, Angelika Wiegele

Publication date: 12 April 2022

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.09075

zbMATH Keywords

ADMMsemidefinite programmingcombinatorial optimizationgraph partitioning

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items

Partitioning through projections: strong SDP bounds for large graph partition problems

Uses Software

• Mosek
• SDPNAL+

Cites Work

• Unnamed Item
• A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
• Graph partitioning using linear and semidefinite programming
• Graph partitioning models for parallel computing
• Linear and quadratic programming approaches for the general graph partitioning problem
• Using a factored dual in augmented Lagrangian methods for semidefinite programming
• Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence
• SDP Relaxations for Some Combinatorial Optimization Problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Quadratic knapsack relaxations using cutting planes and semidefinite programming
• Regularization Methods for Semidefinite Programming
• Computer Solutions of the Traveling Salesman Problem
• Semidefinite programming and combinatorial optimization
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent