SDP-based bounds for graph partition via extended ADMM
From MaRDI portal
Publication:2125076
Abstract: We study two NP-complete graph partition problems, -equipartition problems and graph partition problems with knapsack constraints (GPKC). We introduce tight SDP relaxations with nonnegativity constraints to get lower bounds, the SDP relaxations are solved by an extended alternating direction method of multipliers (ADMM). In this way, we obtain high quality lower bounds for -equipartition on large instances up to vertices within as few as five minutes and for GPKC problems up to vertices within as little as one hour. On the other hand, interior point methods fail to solve instances from due to memory requirements. We also design heuristics to generate upper bounds from the SDP solutions, giving us tighter upper bounds than other methods proposed in the literature with low computational expense.
Recommendations
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- Partitioning through projections: strong SDP bounds for large graph partition problems
- Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
- An efficient semidefinite programming relaxation for the graph partition problem
- Semidefinite programming relaxations for the graph partitioning problem
- scientific article; zbMATH DE number 2088028
- Graph partitioning using linear and semidefinite programming
- An improved rounding method and semidefinite programming relaxation for graph partition
- scientific article; zbMATH DE number 1182569
- Spectral bounds for graph partitioning with prescribed partition sizes
Cites work
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Computer Solutions of the Traveling Salesman Problem
- Graph partitioning models for parallel computing
- Graph partitioning using linear and semidefinite programming
- Improved approximation algorithms for MAX k-CUT and MAX BISECTION
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Linear and quadratic programming approaches for the general graph partitioning problem
- Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Quadratic knapsack relaxations using cutting planes and semidefinite programming
- Regularization methods for semidefinite programming
- Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
- SDP relaxations for some combinatorial optimization problems
- Semidefinite programming and combinatorial optimization
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- Using a factored dual in augmented Lagrangian methods for semidefinite programming
Cited in
(8)- Partitioning through projections: strong SDP bounds for large graph partition problems
- Solving graph equipartition SDPs on an algebraic variety
- Multi-objective k-way parallel hypergraph partitioning with proximal gradient algorithm
- Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems
- Computing the edge expansion of a graph using semidefinite programming
- Constraint hypergraph partitioning problems via recursive bipartition algorithm based on improved Dai-Kou conjugate gradient algorithm
- Edge expansion of a graph: SDP-based computational strategies
- Application of the Lovász-Schrijver operator to compact stable set integer programs
This page was built for publication: SDP-based bounds for graph partition via extended ADMM
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2125076)
