1
$\begingroup$

The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$.

I am trying to prove that 0-1-INT-PROG is NP-Hard by reducing SUBSET-SUM to it.

My attempt:

Given an instance of SUBSET-SUM $<\{a_1, a_2, \cdots, a_n\}, k>$ we construct an instance of 0-1-INT-PROG $<[a_1, a_2, \cdots, a_n], [k]>$.

Claim: $<\{a_1, a_2, \cdots, a_n\}, k> \in $ SUBSET_SUM if and only if $<[a_1, a_2, \cdots, a_n], [k]> \in $ 0-1-INT-PROG.

proof of forward direction. When there exists a subset $S' \subseteq S$ whose sum is $k$, for each $a_i \in S'$, let $x_i = 1$. If $x_i \not \in S'$, then $x_i = 0$. Then $x$ is an $n$-vector which achieves $[a_1, a_2, \cdots, a_n] \cdot x = k$. So $<[a_1, a_2, \cdots, a_n], [k]> \in $ 0-1-INT-PROG.

Question:

When I have tried to prove the other direction I run into a problem. Namely, just because there exists an $x$ vector with $[a_1, a_2, \cdots, a_n] \cdot x \leq k$, does not imply that there exists a subset $S' \subseteq S$ whose sum is $k$, because of the less than or equals to.

So how can I approach the backwards direction?

$\endgroup$
1
$\begingroup$

Let $\langle S, k \rangle$ be an instance of subset sum, where $S=\{a_1, a_2, \dots, a_n\}$. Construct an $0$-$1$-integer program with $n$ binary variables $x_1, \dots, x_n$ and the following constraints:

$$ \begin{align} a_1x_1+a_2 x_2+ \dots+a_n x_n &\le k \\ -a_1x_1-a_2 x_2 - \dots-a_n x_n &\le -k \end{align} $$

Or, in matrix form: $A = \begin{bmatrix} a_1 & a_2 & \dots & a_n \\ -a_1 & -a_2 & \dots & -a_n \end{bmatrix}$ and $b=\begin{bmatrix} k \\ -k\end{bmatrix}$.

If you have a solution $S' \subseteq S$ to the subset sum instance, then you can pick $x$ as the characteristic vector of $S'$ to satisfy the constraints (as you correctly point out in your question). I.e., set $x_i = 1$ if and only if $a_i \in S'$ so that $Ax = \begin{bmatrix} k \\ -k\end{bmatrix} = b$.

On the other hand, if $Ax \le b$ then the first constraint is $a_1 + a_2 + \dots + a_n \le k$ and second constraint implies $a_1 + a_2 + \dots + a_n \ge k$. Then, we necessarily have $a_1 + a_2 + \dots + a_n = k$, showing that $S' = \{ a_i \mid x_i = 1\}$ is a solution to the subset sum instance.

$\endgroup$
1
  • $\begingroup$ So we add a constraint to satisfy the backward direction. I like it, thank you. $\endgroup$ – Tom Finet Apr 27 at 18:10

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.