Multidimensional assignment problem: Difference between revisions

Revision as of 16:28, 17 February 2022

Revision as of 16:28, 17 February 2022

Line 16:

==Formal definition==

Various formulations of this problem can be found in the literature. Using cost-functions, the '''<math>D</math>{{ndash}}dimensional assignment problem''' (or '''<math>D</math>{{ndash}}MAP''') can 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{rR}_+</math>, . Findfind <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>