Content deleted Content added
short description |
Citation bot (talk | contribs) m Alter: title. Add: title-link, hdl, pages. Removed URL that duplicated unique identifier. Removed accessdate with no specified URL. Formatted dashes. | You can use this bot yourself. Report bugs here.| Activated by User:Marianne Zimmerman |
||
Line 31:
== 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 (constant) factor, unless P = NP.<ref>{{Cite journal|
|last1 = Sahni|first1 = Sartaj
|last2 = Gonzalez |first2 = Teofilo
|date = July 1976
|volume=23 |issue=3
|pages = 555–565
|journal = Journal of the ACM|doi = 10.1145/321958.321975|pmid = |hdl = 10338.dmlcz/103883
}}</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 51:
{{Reflist}}
;Sources
* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title =
==External links==
| |||