Multidimensional assignment problem: Difference between revisions

Revision as of 11:18, 13 August 2023

Latest revision as of 13:34, 13 April 2024

(3 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Generalization of linear assignment problem from two to multiple dimensions}}

The '''multidimensional assignment problem''' (MAP) is a fundamental [[combinatorial optimization]] problem which was introduced by [[William Pierskalla]].<ref name="Pier68">{{cite journal |last=Pierskalla |first=William P. |title=Letter to the Editor—The Multidimensional Assignment Problem | journal=Operations Research |publisher=INFORMS |date=1968 |volume=16 |issue=2 |pages=422–431 |doi=10.1287/opre.16.2.422 |doi-access=free }}</ref> This problem can be seen as a generalization of the linear [[assignment problem]].<ref name="Pasi21">{{Cite arXiv|last1=Kammerdiner|first1=Alla|last2=Semenov|first2=Alexander|last3=Pasiliao|first3=Eduardo |date=2021|title=Multidimensional Assignment Problem for multipartite entity resolution|class=cs.DM |eprint=2112.03346}}</ref> In words, the problem can be described as follows:

: An instance of the problem has a number of ''agents'' (i.e., ''cardinality'' parameter) and a number of ''job characteristics'' (i.e., ''dimensionality'' parameter) such as task, machine, time interval, etc. For example, an agent can be assigned to perform task X, on machine Y, during time interval Z. Any agent can be assigned to perform a job with any combination of unique job characteristics at some ''cost''. These costs may vary based on the assignment of agent to a combination of job characteristics - specific task, machine, time interval, etc. The problem is to minimize the ''total cost'' of assigning the agents so that the assignment of agents to each job characteristic is an [[injective function]], or [[one-to-one function]] from agents to a given job characteristic.

Line 12:

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

is minimized.<ref>{{Cite journal|last1=Karapetyan|first1=Daniel|last2=Gutin|first2=Gregory|date=2011-06-01|title=Local search heuristics for the multidimensional assignment problem|url=httpshttp://doirepository.org/10essex.1007ac.uk/s10732-010-9133-322073/1/0806.3258v6.pdf|journal=Journal of Heuristics|language=en|volume=17|issue=3|pages=201–249|doi=10.1007/s10732-010-9133-3|s2cid=3446729 |issn=1572-9397}}</ref>

=== Problem parameters ===

Line 36:

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

*[[Particle physics|Elementary particle physics]]<ref>{{Cite journal|last1=Pusztaszeri|first1=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|s2cid=2002168 }}</ref>

*[[Medical alarm|Fall detection in elderly with small wearable devices]]<ref>{{Cite journal|last1=Kammerdiner|first1=Alla R.|last2=Guererro|first2=Andre N.|date=2019|title=Data-driven combinatorial optimization for sensor-based assessment of near falls|url=http://link.springer.com/10.1007/s10479-017-2585-1|journal=Annals of Operations Research|language=en|volume=276|issue=1–2|pages=137–153|doi=10.1007/s10479-017-2585-1|s2cid=254223885 |issn=0254-5330|url-access=subscription}}</ref>

== References ==

Line 43:

[[Category:Combinatorial optimization]]

https://issuu.com/ostraky/docs/the_top_5_english_coursework_help_strategies_for_t