Quadratic assignment problem: Difference between revisions

Revision as of 12:46, 17 November 2023

Latest revision as of 00:22, 16 April 2025

(4 intermediate revisions by 4 users not shown)

Line 11:

==Formal mathematical definition==

{{unreferenced-section|date=April 2024}}

The formal definition of the quadratic assignment problem is as follows:

Line 25:

In matrix notation:

:<math>\min_{X\in\Pi_n} \operatorname{trace}(WXDXWXD^TX^T)</math>

where <math>\Pi_n</math> is the set of <math>n \times n</math> permutation matrices, <math>W</math> is the weight matrix and <math>D</math> is the distance matrix.

Line 31:

== Computational complexity ==

The problem is [[NP-hard]], so there is no known [[algorithm]] for solving this problem in [[Time complexity|polynomial time]], and even small instances may require long computation time. It was also proven that the problem does not have an approximation algorithm running in polynomial time for any (constant) factor, unless P = NP.<ref>{{Cite journal|title = P-Complete Approximation Problems

|last1 = Sahni|first1 = Sartaj

|last2 = Gonzalez |first2 = Teofilo

Line 43:

In addition to the original plant ___location formulation, QAP is a mathematical model for the problem of placement of interconnected [[electronic component]]s onto a [[printed circuit board]] or on a [[integrated circuit|microchip]], which is part of the [[place and route]] stage of [[computer aided design]] in the electronics industry.

The QAP has also been used to model the cost of character placement on a keyboard. In this case, the locations are keys on the keyboard and their pairwise distances correspond to the time required to press a given pair of keys. The facilities are characters and their weights are proportional to how often the given pair of characters occur in a text corpus. This type of QAP model was used in the design of the French keyboard standard (NF Z71-300).<ref name="t142">{{cite book | last=John | first=Maximilian | last2=Karrenbauer | first2=Andreas | title=Mathematical Optimization Theory and Operations Research | chapter=Dynamic Sparsification for Quadratic Assignment Problems | publisher=Springer International Publishing | publication-place=Cham | volume=11548 | date=2019 | isbn=978-3-030-22628-2 | doi=10.1007/978-3-030-22629-9_17 | page=232–246|url=https://resources.mpi-inf.mpg.de/keyboardoptimization/MOTOR2019/MOTOR2019.pdf}}</ref>

==See also==

Line 48 ⟶ 50:

== References ==

;Notes

{{Reflist}}

;Sources

== Other sources ==

* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 0-7167-1045-5| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness }} A2.5: ND43, pg.218.

Line 61 ⟶ 63:

[[Category:NP-hard problems]]

[[Category:Combinatorial optimization]]

[[Category:Operations research]]