# Optimizing a matrix

input: $b_1,b_2,...,b_n$ positive integers. $a_1<a_2<...a_n$ positive integers output: positive integer

I'm given

$b_1$ columns of the form $\left( \begin{array}{ccc} 1 \\ 0 \\ 0 \\ .\\ .\\ .\\ 0 \end{array} \right)$ $b_2$ columns of the form $\left( \begin{array}{ccc} 0 \\ 1 \\ 0 \\ .\\ .\\ .\\ 0 \end{array} \right)$ … $b_n$ columns of the form $\left( \begin{array}{ccc} 0 \\ 0 \\ 0 \\ .\\ .\\ .\\ 1 \end{array} \right)$ and $b_1+...+b_n$ zero columns. With these columns several $n\times 2(b_1+...+b_n)$ matrices can be made. Notice that those matrices will have at most one '1' in each column.

$a_1,...,a_n$ are positions in rows 1,2 etc. For example $a_1$ is the position $(1,a_1)$.

I'd like to keep every '1' in each row as close as possible to the given $a_{row}$.

What is the best possible minimum distance I can have? To be precise, there is a Matrix that the maximum distance (some '1' has from $a_{row}$) is the minimum of all the other maximum possible distances of all the other Matrices. What is that distance?

I'm not interested in the Matrix that will give me that minimum distance only in the distance itself. Is there an efficient algorithm that computes it?

$\left( \begin{array}{ccc} 1 & 1 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&1\end{array} \right)$ for $a_1=2,a_7=6$ Is a Matrix with the property we want, as is the following one $\left( \begin{array}{ccc} 0 & 1 &1 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&1\end{array} \right)$

distance here is 1 on the contrary the following matrix is not

$\left( \begin{array}{ccc} 1 & 0 &0 & 1 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&1\end{array} \right)$ here the distance is 2.

-
This is very closely related to this question. If you're the same user, this is very bad style; you should have linked to the related question and explained the difference between them, or at the very least asked them from the same account instead of forcing people to find the other one by a general search. If you're not the same user, how come you have such a similar user name and asked such a similar question? – joriki Dec 2 '12 at 15:42