An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
From MaRDI portal
Publication:2967612
DOI10.1287/IJOC.1120.0542zbMath1356.90104OpenAlexW2167345674MaRDI QIDQ2967612
Publication date: 1 March 2017
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.1120.0542
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (13)
Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ Graph bisection revisited ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems ⋮ New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph ⋮ A semidefinite relaxation based global algorithm for two-level graph partition problem ⋮ An exact approach for the multi-constraint graph partitioning problem ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ A two-level graph partitioning problem arising in mobile wireless communications ⋮ Projection results for the \(k\)-partition problem ⋮ Engineering Branch-and-Cut Algorithms for the Equicut Problem ⋮ Semidefinite programming and eigenvalue bounds for the graph partition problem
Uses Software
Cites Work
- 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
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Some simplified NP-complete graph problems
- The node capacitated graph partitioning problem: A computational study
- Min-cut clustering
- Semidefinite programming relaxations for the quadratic assignment problem
- Graph partitioning using linear and semidefinite programming
- Graph partitioning and parallel computing
- An improved rounding method and semidefinite programming relaxation for graph partition
- A projection technique for partitioning the nodes of a graph
- A new approach to minimising the frontwidth in finite element calculations
- On semidefinite programming relaxations of maximum \(k\)-section
- Semidefinite programming relaxations for the graph partitioning problem
- The partition problem
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- On Lagrangian Relaxation of Quadratic Matrix Constraints
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Relaxations of Combinatorial Problems Via Association Schemes
- SDP Relaxations for Some Combinatorial Optimization Problems
- A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem
- On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming
- Multiple-way network partitioning
- Approximate graph coloring by semidefinite programming
- An Efficient Heuristic Procedure for Partitioning Graphs
- Solving Graph Bisection Problems with Semidefinite Programming
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing
- Matrix-Lifting Semi-Definite Programming for Detection in Multiple Antenna Systems
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Lower Bounds for the Partitioning of Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
