Encyclopedia

Multidimensional assignment problem

Generalization of linear assignment problem from two to multiple dimensions

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated June 16, 2026

The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by William Pierskalla. 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.

01Formal definition

Various formulations of this problem can be found in the literature. Using cost-functions, the $D$ , dimensional assignment problem (or $D$ , MAP) can be stated as follows:

Given $D$ sets, $A$ and $J_{1},\ldots J_{D-1}$ , of equal size, together with a cost array or multidimensional weight function $C$ : $A\times J_{1}\times \ldots \times J_{D-1}\rightarrow \mathbb {R} _{+}$ , find $D-1$ permutations $\pi _{d}$ : A → $J_{d}$ such that the total cost function:

$\sum _{a\in A}C(a,\pi _{1}(a),\ldots ,\pi _{D-1}(a))$

is minimized.

Problem parameters

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

The dimensionality parameter $D$
The cardinality parameter $N=|A|$ , where $|A|$ denotes the number of elements in $A$ .

Size of cost array

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

Number of feasible solutions

The feasible region or solution space of the MAP is very large. The number $K$ of feasible solutions (the size of the MAP instance) depends on the MAP parameters $D,N$ . Specifically, $K=(N!)^{D-1}$ .

02Computational 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).

03Applications

The problem found application in many domains:

Watch videos about Multidimensional assignment problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Multidimensional assignment problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.