Quadratic assignment problem: Difference between revisions

Content deleted Content added

Revision as of 20:27, 18 August 2024 edit 158.248.64.38 (talk) applications: added French keyboard standard info. ← 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
(One intermediate revision by one other user not shown)
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 Line 63: [[Category:NP-hard problems]] [[Category:Combinatorial optimization]] [[Category:Operations research]]