A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem

DOI10.1287/moor.1090.0419zbMath1218.90161OpenAlexW2157555448MaRDI QIDQ3169078

Henry Wolkowicz, Yichuan Ding

Publication date: 27 April 2011

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.6624

zbMATH Keywords

quadratic assignment probleminterior point methodslarge-scale problemssemidefinite programming relaxations

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Numerical optimization and variational techniques (65K10) Boolean programming (90C09)

Related Items (7)

On Integrality in Semidefinite Programming for Discrete Optimization ⋮ An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem ⋮ On New Classes of Nonnegative Symmetric Tensors ⋮ Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation ⋮ A note on convex relaxations for the inverse eigenvalue problem ⋮ Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting ⋮ Convex graph invariant relaxations for graph edit distance

Uses Software

• QAPLIB

This page was built for publication: A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem