Revision as of 21:02, 30 September 2024 edit Closed Limelike Curves (talk \| contribs) Extended confirmed users, Pending changes reviewers 8,356 edits added Category:Operations research using HotCat ← Previous edit		Latest revision as of 00:22, 16 April 2025 edit undo MrGumballs (talk \| contribs) 401 edits Link suggestions feature: 1 link added. Tags: Visual edit Newcomer task Suggested: add links
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

Quadratic assignment problem: Difference between revisions