<p>This is called the <a href="http://en.wikipedia.org/wiki/Assignment_problem">(linear) assignment problem</a>. It can be solved efficiently through linear programming over the Birkhoff polytope.</p>

CC BY-SA 3.0
2012-01-26T14:59:27.980Z
2012-01-26T14:59:27.980Z
John Watrous
<p>Here's my attempt to explain the problem in mathematical language:</p>

<p>$$
\text{Given square matrix A}
$$
$$
\left(
\begin{array}{cccc}
 a_{1,1} &amp; a_{1,2} &amp; \cdots &amp; a_{1,N} \\
 a_{2,1} &amp; a_{2,2} &amp; \cdots &amp; a_{2,N} \\
 \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
 a_{N,1} &amp; a_{N,2} &amp; \cdots &amp; a_{N,N}
\end{array}
\right)
$$</p>

<p>Find a minimal sum of $N$ elements such that no two elements are in the same row or column. In other words, find $$\min_{\sigma\in S_N}\left\{\sum_{i=1}^Na_{i,\sigma(i)}\right\},$$ where $S_N$ is the set of permutations on $\{1,\ldots,N\}$.</p>

<p>Is there a standard name for this problem?</p>

<reference-request><optimization><terminology>
Minimal sum of matrix elements
Max
# Minimal sum of matrix elements

(Asked by: username_0 on 2012-01-26)

Here's my attempt to explain the problem in mathematical language:

$$
\text{Given square matrix A}
$$
$$
\left(
\begin{array}{cccc}
a\_{1,1} & a\_{1,2} & \cdots & a\_{1,N} \\
a\_{2,1} & a\_{2,2} & \cdots & a\_{2,N} \\
\vdots & \vdots & \ddots & \vdots \\
a\_{N,1} & a\_{N,2} & \cdots & a\_{N,N}
\end{array}
\right)
$$

Find a minimal sum of $N$ elements such that no two elements are in the same row or column. In other words, find $$\min\_{\sigma\in S\_N}\left\{\sum\_{i=1}^Na\_{i,\sigma(i)}\right\},$$ where $S\_N$ is the set of permutations on $\{1,\ldots,N\}$.

Is there a standard name for this problem?

**Tags:** reference-request, optimization, terminology


---

## 1 answers

### Answer by username_1 on 2012-01-26. Score: 11 | Accepted answer

This is called the [(linear) assignment problem](http://en.wikipedia.org/wiki/Assignment_problem). It can be solved efficiently through linear programming over the Birkhoff polytope.


---

