A Survey of the Quadratic Assignment Problem

By Abdel Nasser, H. Zaied, L. Abd, E. Shawky. 2014

373 citations recorded by the source corpus.

Subfields: Mathematical Optimization, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Joint Discovery of Object States and Manipulation Actions (2017, background): “Problem (1) is NP-hard in general [31] due to its specific integer constraints.”
Federated Learning with Matched Averaging (2020, background): “This is a quadratic assignment problem known to be NP-hard (Loiola et al., 2007).”
Computational Optimal Transport (2018, background): “This is a nonconvex problem, which can be recast as a quadratic assignment problem [Loiola et al., 2007] and is in full generality NP-hard to solve for arbitrary inputs.”
A comprehensive survey on point cloud registration (2021, background): “The optimization of graph matching belongs to the quadratic assignment problem (QAP) [62], which is an NP-hard problem [34].”
SuperGlue: Learning Feature Matching With Graph Neural Networks (2019, background): “Graph matching problems are usually formulated as quadratic assignment problems, which are NP-hard, requiring expensive, complex, and thus impractical solvers [27].”
Image Reconstruction from Bag-of-Visual-Words (2014, methodology): “QAP is known as an NP-Hard problem and solved mainly by a hybrid of two meta-heuristics [18].”
Optimal rates of statistical seriation (2016, background): “The C1P belongs to a more general class of problems that consist in optimizing various criteria over the discrete set of permutations and that can be recast as examples of the notoriously hard quadratic assignment problem [51].”
Factorized Graph Matching (2016, background): “Over the past three decades, a myriad of approximations to solve the QAP in graph matching have been proposed in computer vision and machine learning (see [12, 30] for a survey).”
Gromov-Wasserstein Averaging of Kernel and Distance Matrices (2016, background): “Matching rows of similarity matrices usually becomes a quadratic assignment problem (Loiola et al., 2007), which is NP-hard.”
ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations (2014, methodology): “Crude oil scheduling 24 [78,109,110] MIQCQP BoxQP 90 [25,142,143] Circles & Polygon nesting 35 [68] Crude oil scheduling 7 [79,80] Multi-period blending 7 [75,76] Natural gas production 3 [81,82,123] Point packing 14 [12] QAP 67 [11,87] Randomly-generated QCQP 135 [15] Reform.”
A review of multimodal image matching: Methods and applications (2021, background): “It usually formulates point set matching s a quadratic assignment problem (QAP) [237].”