On the quadratic assignment problem

By Alan M. Frieze, J. Yadegar. 1983

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

SIGMa: simple greedy matching for aligning large knowledge bases (2012, methodology): “NP-complete problem in operational research [19].”
CliqueCNN: Deep Unsupervised Exemplar Learning (2016, background): “Since X is discrete, the optimization problem (1) is not easier than the Quadratic Assignment Proble which is known to be NP -hardm [1].”
Ant Colony Optimization (2001, unknown): “Note that in an earlier variant of the ANTS-QAP algorithm (Maniezzo & Colorni, 1999), the well-known Gilmore-Lawler lower bound (GLB) (Gilmore, 1962; Lawler, 1963) was applied at each step; however, the GLB requires a computation time of order Oðn(3)Þ.”
Semidefinite programming (2002, result): “3 illustrates the strength of the SDP relaxation on several Nugent problems from QAPLIB compared to other bounds in the literature: Gilmore-Lawler bound (GLB) [6, 14], the projection or elimination bound ELI of [8], and the improved eigenvalue bound EVB3 from [26].”
An Overview of Service Placement Problem in Fog and Edge Computing (2020, unknown): “As other formulations found in the literature we quote: Matching Game [63], Markov Decision Process (MDP) [121], stochastic optimization [111], petri nets[4], potential games [104], quadratic assignment problem [32], general convex optimization [27].”
A Survey of the Quadratic Assignment Problem, with Applications (2003, background): “The Gilmore-Lawler bound (GLB) was one of the first lower bounds ever proposed for the QAP [18, 27].”
Factorized Graph Matching (2016, methodology): “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).”
Guided Local Search (2010, methodology): “Quadratic Assignment Problem (QAP) is one of the most difficult problems in combinatorial optimization.”
Quantum computing for energy systems optimization: Challenges and opportunities (2019, background): “One such fundamental problem from the category of facility location is the quadratic assignment problem [42].”
A Survey of Automatic Parameter Tuning Methods for Metaheuristics (2020, unknown): “In the ﬁrst tuning problem, the iterated local search (ILS) [54] is tuned on quadratic assignment problem [55].”
An enabling framework for master-worker applications on the Computational Grid (2000, background): “Despite its simple statement—to minimize the assignment cost of w facilities to w locations—it is extremely difficult to solve even modest sized instances of the QAP.”