Semidefinite programming and eigenvalue bounds for the graph partition problem
From MaRDI portal
Publication:2349129
DOI10.1007/S10107-014-0817-6zbMATH Open1328.90103arXiv1312.0332OpenAlexW3106367272MaRDI QIDQ2349129FDOQ2349129
Edwin R. Van Dam, Renata Sotirov
Publication date: 19 June 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the sum of weights of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes of graphs and also show how to aggregate additional triangle and independent set constraints for graphs with symmetry. We present an eigenvalue bound for the graph partition problem of a strongly regular graph, extending a similar result for the equipartition problem. We also derive a linear programming bound of the graph partition problem for certain Johnson and Kneser graphs. Using what we call the Laplacian algebra of a graph, we derive an eigenvalue bound for the graph partition problem that is the first known closed form bound that is applicable to any graph, thereby extending a well-known result in spectral graph theory. Finally, we strengthen a known semidefinite programming relaxation of a specific quadratic assignment problem and the above-mentioned matrix-lifting semidefinite programming relaxation by adding two constraints that correspond to assigning two vertices of the graph to different parts of the partition. This strengthening performs well on highly symmetric graphs when other relaxations provide weak or trivial bounds.
Full work available at URL: https://arxiv.org/abs/1312.0332
Recommendations
- An efficient semidefinite programming relaxation for the graph partition problem
- Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
- scientific article; zbMATH DE number 1182569
- Semidefinite programming relaxations for the graph partitioning problem
- Graph bisection revisited
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Semidefinite programming (90C22) Association schemes, strongly regular graphs (05E30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Title not available (Why is that?)
- Spectra of graphs
- Exploiting special structure in semidefinite programming: a survey of theory and applications
- Symmetry groups, semidefinite programs, and sums of squares
- A simple group of order 44,352,000
- Title not available (Why is that?)
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Some simplified NP-complete graph problems
- Semidefinite programming relaxations for the quadratic assignment problem
- On semidefinite programming relaxations of maximum \(k\)-section
- SDP Relaxations for Some Combinatorial Optimization Problems
- Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- Title not available (Why is that?)
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
- Lower Bounds for the Partitioning of Graphs
- Optimal linear labelings and eigenvalues of graphs
- Multiple-way network partitioning
- Solving Graph Bisection Problems with Semidefinite Programming
- Relaxations of Combinatorial Problems Via Association Schemes
- Semidefinite programming relaxations for the graph partitioning problem
- A computational study of graph partitioning
- The pseudo-geometric graphs for generalized quadrangles of order \((3,t)\)
- How Good is the Goemans--Williamson MAX CUT Algorithm?
- A projection technique for partitioning the nodes of a graph
- Semidefinite programs and association schemes
- Bounds for the quadratic assignment problem using the bundle method
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- On Bounding the Bandwidth of Graphs with Symmetry
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing
- Bandwidth, Vertex Separators, and Eigenvalue Optimization
- Graph partitioning and parallel computing
Cited In (12)
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Title not available (Why is that?)
- Graph bisection revisited
- A multilevel analysis of the Lasserre hierarchy
- SDP-based bounds for graph partition via extended ADMM
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- Graph-Based Representations in Pattern Recognition
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- A Copositive Programming Approach to Graph Partitioning
- Partitioning through projections: strong SDP bounds for large graph partition problems
Uses Software
This page was built for publication: Semidefinite programming and eigenvalue bounds for the graph partition problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2349129)
