Semidefinite programming approach for the quadratic assignment problem with a sparse graph

DOI10.1007/S10589-017-9968-8zbMath1415.90071arXiv1703.09339OpenAlexW2601563163MaRDI QIDQ1744907

Amit Singer, Yuehaw Khoo, José F. S. Bravo Ferreira

Publication date: 20 April 2018

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.09339

zbMATH Keywords

semidefinite programmingquadratic assignment problemconvex relaxationgraph matchingalternating direction method of multipliers

Mathematics Subject Classification ID

Semidefinite programming (90C22) Discrete location and assignment (90B80)

Related Items (7)

NMR assignment through linear programming ⋮ A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications ⋮ Learning Markov Models Via Low-Rank Optimization ⋮ A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP ⋮ On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming ⋮ Scalable Semidefinite Programming ⋮ A time-triggered dimension reduction algorithm for the task assignment problem

Uses Software

• Unnamed Item
• SeDuMi
• ADMM_QAP
• BioMagResBank

Cites Work

• An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• A survey for the quadratic assignment problem
• A new relaxation framework for quadratic assignment problems based on matrix splitting
• Fractional isomorphism of graphs
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• ADMM for the SDP relaxation of the QAP
• Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting
• On convex relaxation of graph isomorphism
• 10.1162/15324430260185646
• A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives
• P-Complete Approximation Problems
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• An Exact Algorithm for the Quadratic Assignment Problem on a Tree
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions

This page was built for publication: Semidefinite programming approach for the quadratic assignment problem with a sparse graph