Content deleted Content added
m Added ref tags |
COPknowledge (talk | contribs) Added major application areas |
||
Line 6:
The '''assignment problem''' is a fundamental [[combinatorial optimization]] problem which was introduced by Pierskalla<ref name="Pier68">{{cite journal |last=Pierskalla |first=William P. |title=Letter to the Editor—The Multidimensional Assignment Problem | journal=Operations Research 16(2) |publisher=INFORMS |date=1968 |volume=16 |issue=2 |page=422-431 |doi=10.1287/opre.16.2.422 |url=https://pubsonline.informs.org/doi/abs/10.1287/opre.16.2.422}}</ref>. This problem can be seen as a generalization of the linear [[assignment problem]]. 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 23:
The problem is generally [[NP-hard]]. In other words, there is no known [[algorithm]] for solving this problem in polynomial time, 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 ==
The problem found application in many domains:
*[[Scheduling (production processes)]] <ref name="Pier68" />
*[[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>{{Cite arXiv|last=Kammerdiner|first=Alla|last2=Semenov|first2=Alexander|last3=Pasiliao|first3=Eduardo |date=2021|title=Multidimensional Assignment Problem for multipartite entity resolution|eprint=2112.03346}}</ref>
*[[Particle physics|Elementary partcile 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]]
== References ==
| |||