Revision as of 12:53, 19 May 2022 edit 185.11.153.229 (talk) →Computational complexity Tag: Reverted ← Previous edit		Revision as of 15:02, 26 May 2022 edit undo Galaktos (talk \| contribs) Extended confirmed users 987 edits Undid revision 1088666204 by 185.11.153.229 (talk) – even if P=NP, that doesn’t change the fact that there is no known algorithm to solve it in polynomial time, IMHO Tag: Undo Next edit →
Line 27: == Computational complexity == The problem is generally [[NP-hard]]. In other words, there is no known [[algorithm]] for solving this problem in polynomial time ~~unless [[P=NP]]~~, and so a long computational time may be needed for solving problem instances of even moderate size (based on dimensionality and cardinality parameters).<ref>{{Cite journal\|last=Nguyen\|first=Duc Manh\|last2=Le Thi\|first2=Hoai An\|last3=Pham Dinh\|first3=Tao\|date=2012-10-12\|title=Solving the Multidimensional Assignment Problem by a Cross-Entropy method\|journal=Journal of Combinatorial Optimization\|volume=27\|issue=4\|pages=808–823\|doi=10.1007/s10878-012-9554-z\|issn=1382-6905}}</ref> == Applications ==

Multidimensional assignment problem: Difference between revisions