Multidimensional assignment problem: Difference between revisions

Revision as of 21:51, 18 February 2022

Revision as of 22:57, 18 February 2022

Line 24:

The multidimensional assignment problem (MAP) has two key parameters that determine ''the size of a problem instance'':

# The '''[[dimension|dimensionality]] parameter''' <math>D</math>

# The '''[[cardrinalitycardinality]] parameter''' <math>N = |A|</math>, where <math>|A|</math> denotedenotes a size of set <math>A</math> or athe number of elements in <math>A</math>.

=== Size of cost array ===

Any problem instance of the MAP with parameters <math>D, N</math> has its specific '''cost array''' <math>C</math>, which consists of <math>N^{D}</math> instance-specific costs/weights parameters <math>C(a,a_1,\ldots,a_{D-1})</math>. Alternatively, <math>N^{D}</math> is the ''size'' of cost array.

=== Number of feasible solutions ===

The [[feasible region|feasibalefeasible region or solution space]] of the MAP is very large. The number <math>K</math> of feasible solutions (or the size of the MAP instance) depends on the MAP parameters <math>D, N</math>. Specifically, <math>K = (N!)^{D-1}</math>.<ref name="Pasi21" />

== Computational complexity ==

Line 42:

*[[Data fusion|Multi-sensor data fusion]] <ref>{{Cite journal|last=Poore|first=Aubrey B.|date=1994|title=Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking|journal=Computational Optimization and Applications|volume=3|issue=1|pages=27-57|doi=10.1007/BF01299390}}</ref>

*[[Record linkage|Record linkage or multipartite entity resolution]] <ref name="Pasi21" />

*[[Particle physics|Elementary partcileparticle physics]] <ref>{{Cite journal|last=Pusztaszeri|first=Jean-François|last2=Rensing|first2=Paul E.|last3=Liebling|first3=Thomas M.|date=1996|title=Tracking elementary particles near their primary vertex: a combinatorial approach|journal=Journal of Global Optimization|volume=9|issue=1|pages=41-64|doi=10.1007/BF00121750}}</ref>

*[[Medical alarm|Fall detection in elderly with small wearable devices]]