Partitioning through projections: strong SDP bounds for large graph partition problems
From MaRDI portal
Publication:6109293
DOI10.1016/j.cor.2022.106088arXiv2205.06788OpenAlexW4310069340MaRDI QIDQ6109293
Renata Sotirov, Frank de Meijer, Shudian Zhao, Angelika Wiegele
Publication date: 4 July 2023
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2205.06788
semidefinite programmingcutting planesaugmented Lagrangian methodsDykstra's projection algorithmgraph partition problems
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
- Alternating direction augmented Lagrangian methods for semidefinite programming
- The MIN-cut and vertex separator problem
- A boundary point method to solve semidefinite programs
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- A cutting plane algorithm for a clustering problem
- A cyclic projection algorithm via duality
- Some simplified NP-complete graph problems
- The node capacitated graph partitioning problem: A computational study
- A branch-and-cut algorithm for the equicut problem
- On the Slater condition for the SDP relaxations of nonconvex sets
- Graph bisection revisited
- ADMM for the SDP relaxation of the QAP
- A projection technique for partitioning the nodes of a graph
- On semidefinite programming relaxations of maximum \(k\)-section
- An exact algorithm for graph partitioning
- Semidefinite programming relaxations for the graph partitioning problem
- Hybrid evolutionary algorithms for graph coloring
- A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
- SDP-based bounds for graph partition via extended ADMM
- Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- The partition problem
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Lower bounds for the bandwidth problem
- Mathematical formulation of quantum circuit design problems in networks of quantum computers
- SDP Relaxations for Some Combinatorial Optimization Problems
- Projection Methods: Swiss Army Knives for Solving Feasibility and Best Approximation Problems with Halfspaces
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- Matrices Associated With the Hitchcock Problem
- An Algorithm for Restricted Least Squares Regression
- On Solving the Quadratic Shortest Path Problem
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- A VLSI decomposition of the deBruijn graph
- Solving Graph Bisection Problems with Semidefinite Programming
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- Scalable Semidefinite Programming
- A better upper bound on the bisection width of de Bruijn networks
- SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- Lower Bounds for the Partitioning of Graphs
