Quadratic assignment problem: Difference between revisions

Revision as of 23:33, 16 August 2014

Revision as of 22:32, 19 September 2014

Line 13:

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

:Given two sets, ''P'' ("facilities") and ''L'' ("locations"), of equal size, together with a [[weight function]] ''w'' : ''P'' × ''P'' → '''[[real number|R]]''' and a distance function ''d'' : ''L'' × ''L'' → '''[[real number|R]]'''. Find the [[bijection]] ''f'' : ''P'' → ''L'' ("assignment") such that the cost function:

::<math>\sum_{a,b\in P}w(a,b)\cdot d(f(a), f(b))</math>

Line 28:

== Computational complexity ==

The problem is [[NP-hard]], so there is no known [[algorithm]] for solving this problem in 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 factor, unless P = NP. <ref>{{Cite journal|url = http://dl.acm.org/citation.cfm?id=321958.321975&coll=DL&dl=GUIDE&CFID=533242734&CFTOKEN=20099075|title = P-Complete Approximation Problems|last = Sahni|first = Sartaj|date = |journal = Journal of the ACM (JACM)|accessdate = |doi = 10.1145/321958.321975|pmid = }}</ref> The [[travelling salesman problem]] may be seen as a special case of QAP if one assumes that the flows connect all facilities only along a single ring, all flows have the same non-zero (constant) value. Many other problems of standard [[combinatorial optimization]] problems may be written in this form.

== Applications ==

Line 38:

== References ==

{{Reflist}}

* {{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}} A2.5: ND43, pg.218.

Line 43 ⟶ 44:

* http://www.seas.upenn.edu/qaplib/ QAPLIB - A Quadratic Assignment Problem Library

* http://issuu.com/spconguy/docs/ant-algorithm-applied-to-the-quadratic-assignment- - A QAP sample application

[[Category:NP-hard problems]]

[[Category:Combinatorial optimization]]