On semidefinite programming relaxations of maximum \(k\)-section (Q1925786): Difference between revisions

The authors revisit semidefinite programming (SDP) relaxations for the maximum \(k\)-section problem, a classical problem of combinatorial optimization. They rely upon a previous SDP relaxation proposed by two of the authors for the quadratic assignment problem. By performing symmetry reduction, they show that the new SDP bound can be obtained more efficiently.

0 references

reviewed by

Didier Henrion

0 references

Mathematics Subject Classification ID

0 references

0 references

graph theory

0 references

combinatorial optimization

0 references

describes a project that uses

SeDuMi

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s10107-012-0603-2

0 references

0 references

0 references

A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem

0 references

Q4251055

0 references

Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

0 references

Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem

0 references

Approximation Algorithms for Maximization Problems Arising in Graph Partitioning

0 references

Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION

0 references

Some simplified NP-complete graph problems

0 references

Symmetry groups, semidefinite programs, and sums of squares

0 references

A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem

0 references

Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices

0 references

Q3961697

0 references

Spreads in strongly regular graphs

0 references

A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems

0 references

Coherent algebras

0 references

A simple group of order 44,352,000

0 references

An improved rounding method and semidefinite programming relaxation for graph partition

0 references

Q4400639

0 references

Graph partitioning using linear and semidefinite programming

0 references

Nonpolyhedral Relaxations of Graph-Bisection Problems

0 references

Copositive and semidefinite relaxations of the quadratic assignment problem

0 references

A comparison of the Delsarte and Lovász bounds

0 references

New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming

0 references

Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

0 references

A .699-approximation algorithm for Max-Bisection.

0 references

Semidefinite programming relaxations for the graph partitioning problem

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1925786

@@ Property / cites work @@
+A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
+Normal rank
@@ Property / cites work @@
+Q4251055
@@ Property / cites work: Q4251055 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
+Normal rank
@@ Property / cites work @@
+Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
+Normal rank
@@ Property / cites work @@
+Some simplified NP-complete graph problems
@@ Property / cites work: Some simplified NP-complete graph problems / rank @@
+Normal rank
@@ Property / cites work @@
+Symmetry groups, semidefinite programs, and sums of squares
+Normal rank
@@ Property / cites work @@
+A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
+Normal rank
@@ Property / cites work @@
+Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
+Normal rank
@@ Property / cites work @@
+Q3961697
@@ Property / cites work: Q3961697 / rank @@
+Normal rank
@@ Property / cites work @@
+Spreads in strongly regular graphs
@@ Property / cites work: Spreads in strongly regular graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
+Normal rank
@@ Property / cites work @@
+Coherent algebras
@@ Property / cites work: Coherent algebras / rank @@
+Normal rank
@@ Property / cites work @@
+A simple group of order 44,352,000
@@ Property / cites work: A simple group of order 44,352,000 / rank @@
+Normal rank
@@ Property / cites work @@
+An improved rounding method and semidefinite programming relaxation for graph partition
+Normal rank
@@ Property / cites work @@
+Q4400639
@@ Property / cites work: Q4400639 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph partitioning using linear and semidefinite programming
+Normal rank
@@ Property / cites work @@
+Nonpolyhedral Relaxations of Graph-Bisection Problems
+Normal rank
@@ Property / cites work @@
+Copositive and semidefinite relaxations of the quadratic assignment problem
+Normal rank
@@ Property / cites work @@
+A comparison of the Delsarte and Lovász bounds
@@ Property / cites work: A comparison of the Delsarte and Lovász bounds / rank @@
+Normal rank
@@ Property / cites work @@
+New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
+Normal rank
@@ Property / cites work @@
+Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
+Normal rank
@@ Property / cites work @@
+A .699-approximation algorithm for Max-Bisection.
@@ Property / cites work: A .699-approximation algorithm for Max-Bisection. / rank @@
+Normal rank
@@ Property / cites work @@
+Semidefinite programming relaxations for the graph partitioning problem
+Normal rank