Multidimensional assignment problem: Difference between revisions

Revision as of 20:19, 16 February 2022

Revision as of 16:27, 17 February 2022

Line 15:

==Formal definition==

Various definitionsformulations are formulated forof this problem can be found in the literature. ForUsing examplecost-functions, the '''multidimensional<math>D</math>{{mdash}}dimensional assignment problem''' (or '''<math>D</math>{{mdash}}MAP''') iscan be stated as follows:

:Given <math>D</math> sets, <math>A</math> and <math>J_1, \ldots J_{D-1}</math>, of equal size, together with a cost [[array]] or multidimensional [[weight function]] <math>C</math> : <math>A \times J_1 \times \ldots \times J_{D-1} \rightarrow \mathbb{r}_+</math> &rarr; '''[[real number|R]]'''. Find <math>D-1</math> [[permutation]]s <math>\pi_{d}</math> : ''A'' &rarr; <math>J_d</math> such that the total [[Loss function|cost function]]:

:Given <math>D</math> sets, <math>A</math> and <math>J_1, \ldots J_{D-1}</math>, of equal size, together with a cost [[array]] or multidimensional [[weight function]] <math>C</math> : <math>A \times J_1 \times \ldots \times J_{D-1}</math> &rarr; '''[[real number|R]]'''. Find <math>D-1</math> [[permutation]]s <math>\pi_{d}</math> : ''A'' &rarr; <math>J_d</math> such that the total [[Loss function|cost function]]:

::<math>\sum_{a\in A}C(a,\pi_{1}(a),\ldots,\pi_{D-1}(a))</math>

is minimized.<ref>{{Cite journal|last=Karapetyan|first=Daniel|last2=Gutin|first2=Gregory|date=2011-06-01|title=Local search heuristics for the multidimensional assignment problem|url=https://doi.org/10.1007/s10732-010-9133-3|journal=Journal of Heuristics|language=en|volume=17|issue=3|pages=201–249|doi=10.1007/s10732-010-9133-3|issn=1572-9397}}</ref>

is minimized.

== Computational complexity ==