On semidefinite programming relaxations of maximum k-section
From MaRDI portal
Publication:1925786
DOI10.1007/S10107-012-0603-2zbMATH Open1263.90056OpenAlexW2171599960WikidataQ56874347 ScholiaQ56874347MaRDI QIDQ1925786FDOQ1925786
Dmitrii V. Pasechnik, Renata Sotirov, E. de Klerk, Cristian Dobre
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
Recommendations
- An efficient semidefinite programming relaxation for the graph partition problem
- Graph bisection revisited
- Approximation Algorithms for Max 3-Section Using Complex Semidefinite Programming Relaxation
- Strengthened semidefinite programming relaxations for the max-cut problem.
- scientific article; zbMATH DE number 1894380
Cites Work
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Symmetry groups, semidefinite programs, and sums of squares
- A simple group of order 44,352,000
- Approximation algorithms for maximization problems arising in graph partitioning
- Title not available (Why is that?)
- 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
- Some simplified NP-complete graph problems
- New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
- A comparison of the Delsarte and Lovász bounds
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- Title not available (Why is that?)
- Spreads in strongly regular graphs
- A .699-approximation algorithm for Max-Bisection.
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- Coherent algebras
- An improved rounding method and semidefinite programming relaxation for graph partition
- Title not available (Why is that?)
- Graph partitioning using linear and semidefinite programming
- Semidefinite programming relaxations for the graph partitioning problem
- Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
Cited In (13)
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- The MIN-cut and vertex separator problem
- Title not available (Why is that?)
- Graph bisection revisited
- Engineering Branch-and-Cut Algorithms for the Equicut Problem
- Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- Semidefinite and Lagrangian relaxations for hard combinatorial problems
- Bipartite sandwiches: Semidefinite relaxations for maximum biclique
- SDP Relaxations for Some Combinatorial Optimization Problems
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- Partitioning through projections: strong SDP bounds for large graph partition problems
- Title not available (Why is that?)
Uses Software
This page was built for publication: On semidefinite programming relaxations of maximum \(k\)-section
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1925786)
