Semidefinite programming relaxations for the graph partitioning problem
From MaRDI portal
Publication:1961466
DOI10.1016/S0166-218X(99)00102-XzbMath0932.90030MaRDI QIDQ1961466
Publication date: 21 March 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Convex programming (90C25) Combinatorial optimization (90C27) Positive matrices and their generalizations; cones of matrices (15B48)
Related Items (31)
Graph bisection revisited ⋮ Sums of random symmetric matrices and quadratic optimization under orthogonality constraints ⋮ Facial reduction algorithms for conic optimization problems ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Gangster operators and invincibility of positive semidefinite matrices ⋮ Efficient Use of Semidefinite Programming for Selection of Rotamers in Protein Conformations ⋮ On semidefinite programming relaxations of maximum \(k\)-section ⋮ Semidefinite approximations for quadratic programs over orthogonal matrices ⋮ Lower bounds for the bandwidth problem ⋮ Strong duality and minimal representations for cone optimization ⋮ Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ A note on the SDP relaxation of the minimum cut problem ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems ⋮ An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem ⋮ Robust optimization of graph partitioning involving interval uncertainty ⋮ An exact approach for the multi-constraint graph partitioning problem ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ A Complementary Column Generation Approach for the Graph Equipartition Problem ⋮ The MIN-cut and vertex separator problem ⋮ Contribution of copositive formulations to the graph partitioning problem ⋮ Preprocessing and Regularization for Degenerate Semidefinite Programs ⋮ Validating numerical semidefinite programming solvers for polynomial invariants ⋮ Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone ⋮ A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem ⋮ Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials ⋮ Congress seat allocation using mathematical optimization ⋮ A note on lack of strong duality for quadratic problems with orthogonal constraints ⋮ Semidefinite programming and eigenvalue bounds for the graph partition problem ⋮ On the Slater condition for the SDP relaxations of nonconvex sets
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A computational study of graph partitioning
- Semidefinite programming relaxations for the quadratic assignment problem
- Very fast simulated re-annealing
- Cones of diagonally dominant matrices
- A projection technique for partitioning the nodes of a graph
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- The lattice of faces of a finite dimensional cone
- On Lagrangian Relaxation of Quadratic Matrix Constraints
- Cones of Matrices and Set-Functions and 0–1 Optimization
- An Efficient Heuristic Procedure for Partitioning Graphs
- Solving Graph Bisection Problems with Semidefinite Programming
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Lower Bounds for the Partitioning of Graphs
This page was built for publication: Semidefinite programming relaxations for the graph partitioning problem
