Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write $C(i,j)$ for the $(i,j)$ entry of $C$. Let $\mathcal{L_n}$ be the set of all $n \times n$ Latin squares. So each $L \in \mathcal{L_n}$ is an $n \times n$ matrix with entries $L_{i,j} \in \{1, \dots, n\}$ and each row $L_{i,*}$ is a permutation on this set.

I am interested in finding

$$ L^* = \arg\min_{L \in \mathcal{L_n}} \sum_{i,j} p_i \, C(j,L_{i,j}) $$

either exactly or with a good approximation method.

If $p = (1, 0, \dots, 0)$, this is the usual minimal cost assignment problem of finding a permutation $\pi$ on $\{1, \dots, n\}$ that minimizes $\sum_{j} C(j,\pi(j))$. This suggests an approximate greedy method to solve the full problem:

  1. Set $L_{1,j} = \pi(j)$ where $\pi$ solves the assignment problem for this cost matrix $C$. Define $\tilde C(i,j) = M$ if $j = \pi(i)$ and $\tilde C(i,j) = C(i,j)$ otherwise, where $M > 0$ is large.
  2. For $i = 1, \dots, n-1$, if the rows $L_{k,*}$ have already been constructed for $k = 1, \dots, i$ and $\tilde C$ is given, solve the minimal cost assignment problem for $\tilde C$. Let $\sigma$ be the resulting permutation. Define $L_{i+1,j} = \sigma(j)$. Replace $\tilde C(r,s)$ with $M$ if $s = \sigma(r)$.

This seems to work fine and it is not hard to see that it always produces a Latin square, if $M$ is sufficiently large. However, this greedy method is by no means optimal, and it does not take $p$ into account.

Any suggestions/pointers/comments?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.