Multidimensional assignment problem
This article, Multidimensional assignment problem, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
![]() | An editor has marked this as a promising draft and requests that, should it go unedited for six months, G13 deletion be postponed, either by making a dummy/minor edit to the page, or by improving and submitting it for review. Last edited by COPknowledge (talk | contribs) 3 years ago. (Update) | ![]() |
The multidimensional assignment problem is a fundamental combinatorial optimization problem which was introduced by Pierskalla[1]. 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.
Alternatively, describing the problem using graph theory:
- The multidimensional assignment problem consists of finding, in a weighted multipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum.
Formal definition
Various definitions are formulated for this problem. For example, the multidimensional assignment problem (or MAP) is stated as
- Given sets, and , of equal size, together with a cost array or multidimensional weight function : → R. Find permutations : A → such that the total cost function:
is minimized.
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).[2]
Applications
The problem found application in many domains:
- Scheduling (production processes) [1]
- Multi-sensor data fusion [3]
- Record linkage or multipartite entity resolution [4]
- Elementary partcile physics [5]
- Fall detection in elderly with small wearable devices
References
- ^ a b Pierskalla, William P. (1968). "Letter to the Editor—The Multidimensional Assignment Problem". Operations Research 16(2). 16 (2). INFORMS: 422-431. doi:10.1287/opre.16.2.422.
- ^ Nguyen, Duc Manh; Le Thi, Hoai An; Pham Dinh, Tao (2012-10-12). "Solving the Multidimensional Assignment Problem by a Cross-Entropy method". Journal of Combinatorial Optimization. 27 (4): 808–823. doi:10.1007/s10878-012-9554-z. ISSN 1382-6905.
- ^ Poore, Aubrey B. (1994). "Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking". Computational Optimization and Applications. 3 (1): 27–57. doi:10.1007/BF01299390.
- ^ Kammerdiner, Alla; Semenov, Alexander; Pasiliao, Eduardo (2021). "Multidimensional Assignment Problem for multipartite entity resolution". arXiv:2112.03346. A bot will complete this citation soon. Click here to jump the queue
- ^ Pusztaszeri, Jean-François; Rensing, Paul E.; Liebling, Thomas M. (1996). "Tracking elementary particles near their primary vertex: a combinatorial approach". Journal of Global Optimization. 9 (1): 41–64. doi:10.1007/BF00121750.