How to partition the rows of a matrix in such a way that every column satisfies a given condition?

Question

The input is: Given a matrix $\mathbf{A}=\left[a_{ij}\right]$ of nonnegative integers for all $i\in\{1,\ldots, m\}$ and $j\in\{1,\ldots, n\}$ (where $n<m$). Nonnegative integers $V_j$ for all $j\in\{1,\ldots,n\}$.

The question is: Find $n$ disjoint sets $S_j$ of $\{1,\ldots,m\}$ such that $$\bigcup\limits_{j=1}^{n} S_j=\{1,\ldots,m\},$$ $$\quad\quad\quad\;\,\sum_{i\in S_j}a_{ij}\geqslant V_j, \forall\,j\in\{1,\ldots,n\}.$$

So for example, given the matrix

$$ \begin{pmatrix} 7 & 4 & 3\\ 3 & 2 & 7\\ 2& 3 & 4\\ 1 & 1& 5\\ 6 & 10 & 8 \end{pmatrix}, $$ where $n=3$, $m=5$ and $V_1=12$, $V_2=10$ and $V_3=5$.

Then, a solution is $S_1=\{1,2,3\}$, $S_2=\{5\}$ and $S_3=\{4\}$.

I think the difficulty of solving this problem comes from the fact that we would like to partition the rows of a given matrix in such a way that every column satisfies a given condition.

Even though the problem seems related to the exact cover problem, I cannot find a good way to solve it.

Can you suggest a method/algorithm that finds solutions to such problem? If it is a known problem, do you know any reference?

Answer 1

As suggested by Yuval Filmus, reduce PARTITION to my problem.

Given an instance of PARTITION, that is a set of nonnegative integers $\{b_1, \ldots, b_k\}$, is there a subset $S\subset\{1,\ldots,k\}$, such that $\sum_{i\in S}b_i=\sum_{i\notin S}b_i=\frac{\sum_{i=1}^kb_i}{2}$?

Let $n=2$, $m=k$, $a_{ij}=b_i$ for all $(i,j)\in\{1,\ldots,k\}\times\{1,2\}$ and $V_1=V_2=\frac{\sum_{i=1}^kb_i}{2}$.

This is clearly created in polynomial-time.

PARTITION is solved if and only if my problem is solved.

1. If PARTITION is solved: there is a set $S\subset\{1,\ldots,k\}$, such that $\sum_{i\in S}b_i=\sum_{i\notin S}b_i=\frac{\sum_{i=1}^kb_i}{2}$. Take $S_1=S$ and $S_2=\{1,\ldots,k\}\backslash S$. Clearly, $S_1\cup S_2=\{1,\ldots,k\}$ and $S_1$ and $S_2$ are disjoint. Further, we have $$\sum_{i\in S_1}a_{i1}=\sum_{i\in S_1}b_i=V_1\geqslant V_1,\\ \sum_{i\in S_2}a_{i2}=\sum_{i\in S_2}b_i=V_2\geqslant V_2,$$ and my problem is solved.

2. If my problem is solved: there are disjoint $S_1$ and $S_2$ such that $$S_1\cup S_2=\{1,\ldots,k\},\\ \sum_{i\in S_1}a_{i1}=\sum_{i\in S_1}b_i\geqslant V_1,\\ \sum_{i\in S_2}a_{i2}=\sum_{i\in S_2}b_i\geqslant V_2.$$ Since $V_1=V_2=\frac{\sum_{i=1}^kb_i}{2}$ and $\sum_{i\in S_1}b_i+\sum_{i\in S_2}b_i=\sum_{i=1}^kb_i$, we must have $$\sum_{i\in S_1}b_i=\sum_{i\notin S_2}b_i=\frac{\sum_{i=1}^kb_i}{2},$$ and PARTITION is solved.

Therefore, my problem is NP-hard.

To solve the problem, let us write it as integer programming problem as suggested by Yuval Filmus. To do so, introduce the binary variable $x_{ij}$ that is equal to $1$, if $i$ is in set $S_j$, and, $0$ otherwise.

\begin{align} & {\underset{\mathbf{ x }}{\text{maximize}}} & & 0\\[6pt] & \text{subject to} & & \sum_{i=1}^ma_{ij}x_{ij}\geqslant V_j,\forall\, j\in\{1,\ldots,n\},\tag{C1}\\[6pt] & & & \sum_{j=1}^nx_{ij}=1, \forall\, i\in\{1,\ldots,m\},\tag{C2}\\[6pt] & & & x_{ ij }\in\{0, 1\}, \forall (i,j)\in\{1,\ldots,k\}\times\{1,\ldots,n\}\tag{C3}. \end{align}

Even though this solves my problem, I need to develop a greedy algorithm for it, can I do that?