Revision as of 19:10, 26 June 2005 edit Grotmol (talk \| contribs) 3 edits →[[Computational complexity]]: It is not correct that Travellling Salesman is a special case of the Quadratic Assignment Problem. ← Previous edit		Revision as of 19:17, 26 June 2005 edit undo Grotmol (talk \| contribs) 3 edits →[[Computational complexity]]: Wrote ramifications of being NP-hard more exact. Next edit →
Line 22: == [[Computational complexity]] == The problem is [[NP-hard]], ~~i.e.,~~so ~~requires~~there ~~long~~is ~~computation~~no known [[algorithm]] for solving this problem in polynomial time, and even itsmall ~~its~~instances ~~simplified~~may ~~cases,~~require elong computation time.~~g.,~~ The simplified case when all flows are equal to 1 is also NP-hard. Many other problems of standard [[combinatorial optimization]] problems may be written in this form. ~~Many other problems of standard [[combinatorial optimization]] problems may be written in this form.~~ == Applications ==

Quadratic assignment problem: Difference between revisions