4
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

This is called the (linear) assignment problem. It can be solved efficiently through linear programming over the Birkhoff polytope.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.