3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is NP-complete by reduction from SUBSET-SUM or PARTITION (exercise). $\endgroup$ – Yuval Filmus Nov 17 '16 at 15:15
  • $\begingroup$ Thank you. Do you know how can we solve this kind of problem? I found in Wikipedia Algorithm X due to Knuth that solves the exact cover problem but I cannot transform it to my problem. $\endgroup$ – drzbir Nov 17 '16 at 15:31
  • 1
    $\begingroup$ You can formulate it as an integer programming problem and run a solver, hoping for the best. $\endgroup$ – Yuval Filmus Nov 17 '16 at 15:32
3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thanks for writing up a detailed answer. One comment: please don't use 'answers' to ask new questions or follow-up questions. Instead, you should use the 'Ask Question' button in the upper-right to ask a new question. If you do that, make sure you tell us what your exact question is (are you looking for an exact solution or an approximation algorithm or a heuristic?), what your thoughts are, and what approaches you've considered and rejected. $\endgroup$ – D.W. Nov 18 '16 at 17:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.