On semidefinite programming relaxations of maximum \(k\)-section
From MaRDI portal
Publication:1925786
DOI10.1007/s10107-012-0603-2zbMath1263.90056WikidataQ56874347 ScholiaQ56874347MaRDI QIDQ1925786
Renata Sotirov, Cristian Dobre, Dimitrii V. Pasechnik, Etienne de Klerk
Publication date: 19 December 2012
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-012-0603-2
90C22: Semidefinite programming
Related Items
Partitioning through projections: strong SDP bounds for large graph partition problems, Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, The MIN-cut and vertex separator problem, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, Graph bisection revisited, Semidefinite programming and eigenvalue bounds for the graph partition problem, SDP Relaxations for Some Combinatorial Optimization Problems, Engineering Branch-and-Cut Algorithms for the Equicut Problem, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Spreads in strongly regular graphs
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Coherent algebras
- Some simplified NP-complete graph problems
- Graph partitioning using linear and semidefinite programming
- An improved rounding method and semidefinite programming relaxation for graph partition
- Symmetry groups, semidefinite programs, and sums of squares
- Semidefinite programming relaxations for the graph partitioning problem
- A simple group of order 44,352,000
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
- A comparison of the Delsarte and Lovász bounds
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
- A .699-approximation algorithm for Max-Bisection.
