# Algorithm to calculate a maximal string from a matrix.

I have stumbled upon an interesting question whilst working on my thesis. You are given a matrix of pairwise distinct integers $$A=(a_{i,j})$$ with $$1\leq i\leq k$$ and $$1\leq j \leq r$$ and a tuple $$(b_1, \dots, b_r)$$ such that $$\sum_{i=1}^r b_i=k$$.

You have to calculate the lexicographic maximal string $$(a_{i_1, j_1}, a_{i_2, j_2}, \dots, a_{i_k, j_k})$$ such that no $$a_{i,j}$$'s are from the same column and the number of $$a_{i,j}$$'s from row $$l$$ is exactly $$b_l$$ and $$a_{i_1, j_1}.

Are there any known, efficient, algorithms to do this?

An example would be: $$A= \begin{pmatrix} 1 & 4 &3 \\ 5&2&6 \end{pmatrix}$$ and $$b=(2,1)$$ The solution here would be $$(3,4,5)$$.

• 1) You should give an example. 2) A certain similarity with questions on Young tableaux. Commented Mar 6 at 16:54
• I added an example, could you maybe explain to which questions on Young tableaux it is similar? Commented Mar 6 at 20:26
• If rows go from $1$ to $k$, $b$ indices should do the same? Commented Mar 6 at 21:53
• This looks a bit like maximum weighted bipartite $b$-matching (which asks to find a set of coefficients from a matrix maximizing the total sum, with conditions imposed on rows and columns for the number of selected elements) Commented Mar 6 at 22:03

This can be solved in polynomial time.

Bipartite $$b$$-matching problem

Lets recall the bipartite $$b$$-matching problem (formulated in terms of matrices):

Let $$M\in\mathcal{M}_{k, r}$$ be a boolean matrix. For each row $$i$$ and each column $$j$$, we have coefficients $$b_{r_i}, b_{c_j}\in \mathbb{N}$$ indicating the number of elements that should be selected in the corresponding row of column. We have $$\sum_{i=1}^k b_{r_i} = \sum_{j=1}^r b_{c_j}$$. The bipartite $$b$$-matching problem asks if it is possible to find a set of True elements satisfying the requirements on every row and column.

The algorithm

Let's turn back to the problem.

We sort the values in the matrix by decreasing order and number these from $$v_1$$ to \$v_{kr}.

We first want to see if it is possible to find a string beginning by $$a_r$$ (that's the best we can hope)

We set $$b_{r_i} = b_i$$ for all $$i$$ and $$b_{c_j} = 1$$ for all column. We set to true $$a_1$$ to $$a_{r-1}$$ and we $$a_r$$ as selected (this is not an inconvenience to force it to be selected, we can reduce to the classical $$b$$-matching problem by decreasing the $$b$$ values by $$1$$ on its row and its column). If we can find a $$b$$-matching for this problem, this is all good, this means that we can choose as a string $$a_ra_{r-1}...a_1$$.

If not, we set to true $$a_r$$ and force $$a_{r+1}$$ to be selected. We keep going like this until we find a satisfiable $$b$$-matcing problem (this will happen at some point.

Once we find a value for the first character of the string, we delete the corresponding column (or just decrease the corresponding $$b$$-values by one), and we repeat the same thing from the start to find the second character, and so one.

Clearly, this will require a polynomial number of steps, and the $$b$$-matching problem is solvable in polynomial time.

How to solve the bipartite $$b$$-matching problem

They are a lot of specialized algorithms that were developed for $$b$$-matching. For bipartite $$b$$-matching, you can also formulate it as a linear program (thanks to total unimodularity).

In your case, because you have only $$1$$-values for the columns, you have an efficient reduction for standard bipartite matching, for which it is easier to find implementations: just duplicate each row $$i$$ $$b_{r_i}$$ times.