Content deleted Content added
m Pbrks moved page Multidimensional assignment problem (MAP) to Multidimensional assignment problem: no need for DAB |
Undid revision 1127559408 by Herikabhatt (talk) that introduces irrelevant spam link |
||
| (16 intermediate revisions by 11 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
: 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.
Alternatively, describing the problem using graph theory:
:The multidimensional assignment problem consists of finding, in a [[weighted graph|weighted]] [[multipartite graph]], a [[Matching (graph theory)|matching]] of a given size, in which the sum of weights of the edges is minimum.<ref>{{Cite journal|
==Formal definition==
Line 12:
::<math>\sum_{a\in A}C(a,\pi_{1}(a),\ldots,\pi_{D-1}(a))</math>
is minimized.<ref>{{Cite journal|
=== Problem parameters ===
The multidimensional assignment problem (MAP) has two key parameters that determine ''the size of a problem instance'':
# The '''[[dimension
# The '''[[cardinality]] parameter''' <math>N = |A|</math>, where <math>|A|</math> denotes the 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>. <math>N^{D}</math> is the ''size'' of cost array.
=== Number of feasible solutions ===
Line 27:
== Computational complexity ==
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|
== Applications ==
The problem found application in many domains:
*[[Scheduling (production processes)]]
*[[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=
*[[Record linkage|Record linkage or multipartite entity resolution]]
*[[Particle physics|Elementary particle physics]]<ref>{{Cite journal|
*[[Medical alarm|Fall detection in elderly with small wearable devices]]<ref>{{Cite journal|
== References ==
{{reflist}}
[[Category:Combinatorial optimization]]
| |||