Semidefinite programming and eigenvalue bounds for the graph partition problem
From MaRDI portal
Publication:2349129
DOI10.1007/s10107-014-0817-6zbMath1328.90103arXiv1312.0332OpenAlexW3106367272MaRDI QIDQ2349129
Renata Sotirov, van Dam, Edwin R.
Publication date: 19 June 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.0332
Semidefinite programming (90C22) Association schemes, strongly regular graphs (05E30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Computational study of valid inequalities for the maximum \(k\)-cut problem, Graph bisection revisited, The Maximum k-Colorable Subgraph Problem and Related Problems, Computational study of a branching algorithm for the maximum \(k\)-cut problem, 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 multilevel analysis of the Lasserre hierarchy
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- Spectra of graphs
- Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Bounds for the quadratic assignment problem using the bundle method
- Exploiting special structure in semidefinite programming: a survey of theory and applications
- Optimal linear labelings and eigenvalues of graphs
- Some simplified NP-complete graph problems
- A computational study of graph partitioning
- Semidefinite programming relaxations for the quadratic assignment problem
- Graph partitioning and parallel computing
- Symmetry groups, semidefinite programs, and sums of squares
- A projection technique for partitioning the nodes of a graph
- On semidefinite programming relaxations of maximum \(k\)-section
- Semidefinite programming relaxations for the graph partitioning problem
- Semidefinite programs and association schemes
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- A simple group of order 44,352,000
- Relaxations of Combinatorial Problems Via Association Schemes
- SDP Relaxations for Some Combinatorial Optimization Problems
- Bandwidth, Vertex Separators, and Eigenvalue Optimization
- On Bounding the Bandwidth of Graphs with Symmetry
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- Multiple-way network partitioning
- How Good is the Goemans--Williamson MAX CUT Algorithm?
- 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
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Lower Bounds for the Partitioning of Graphs
- The pseudo-geometric graphs for generalized quadrangles of order \((3,t)\)
