Quadratic assignment problem: Difference between revisions

Revision as of 21:25, 26 February 2006

Revision as of 22:58, 29 August 2006

Line 11:

The formal definition of the quadratic assignment problem is

: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 30:

== References ==

* {{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 | id = ISBN 07167104550-7167-1045-5}} A2.5: ND43, pg.218.

[[Category:NP-complete problems]]