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
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
