I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here:

Suppose you have a matrix $A\in\mathbb{N}^{n\times m}$ with integer entries. I want to partition the columns of $A$ into $k$ groups (or $k$ matrices), such that the sum of the minima of every row in each group is minimized. To illustrate: Suppose $$ A = \left[ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5\\ 3 & 4 & 5 & 6 & 7\\ 6 & 5 & 4 & 3 & 2\\ \end{array} \right]\text{ .} $$

If I partition the columns into the following three matrices $$ A_1 = \left[ \begin{array}{cc} \color{red}1 & 2 \\ \color{red}3 & 4 \\ 6 & \color{red}5 \\ \end{array} \right],\qquad A_2 = \left[ \begin{array}{ccccc} \color{red}3 & 5\\ \color{red}5 & 7\\ 4 & \color{red}2\\ \end{array} \right],\qquad A_3 = \left[ \begin{array}{ccccc} \color{red}4\\ \color{red}6\\ \color{red}3\\ \end{array} \right], $$

the "score" would be $(1+3+5)+(3+5+2)+(4+6+3)=32$, the sum of all the red entries (which are the minimal entries in each row).

Also, there is a given minimum size $M$ for the groups, so each group must have at least $M$ columns.

Is there any feasible algorithm for minimizing this?

  • $\begingroup$ Just to be clear, in this example $k=3$? Is there a requirement that each group is nonempty? $\endgroup$ – Albert Hendriks Jan 6 at 0:57
  • $\begingroup$ @Albert Hendriks yes, the example is k=3. There may be restrictions on the size of the groups, I forgot to add. I updated my question accordingly $\endgroup$ – thegentlecat Jan 6 at 2:19

Your Answer

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

Browse other questions tagged or ask your own question.