Cheap and Secure Web Hosting Provider : See Now

[Solved]: Restricted Integer Programming

, , No Comments
Problem Detail: 

The integer feasibility problem is NP-complete:

$Ax=b, x \geq 0, x \mbox{ integer}$

$A$ contains elements in $\mathbb{R}$

If we restrict this:

$A$ contains only elements in:

  1. $\{1,0\}$
  2. $\{1,0,-1\}$
  3. $\mathbb{N}$
  4. $\mathbb{Z}$

Does this change anything in term of hardness?

Can all these problems be reduced to each other?

(Can it be for example that there is polynominaltime-algorithm for 1. but not for 4.?)

Asked By : user3613886

Answered By : D.W.

All four problems are NP-complete.

Let me start by proving two easy results:

  • Your problem #3 is NP-complete, even when the matrix has only a single row, as explained here: Complexity of a subset sum variant.

  • This implies that #4 is NP-complete as well, as #3 is a special case of #4.

Now for the strong result: Your problem #1 is NP-complete. The proof of this is a bit more involved, but I'll show a reduction from ZOE to your #1, where ZOE is a problem that is known to be NP-complete.

In particular, here is the definition of ZOE:

ZERO-ONE EQUATIONS (ZOE)
Input: a $m\times n$ matrix $A$, all of whose entries are 0 or 1
Goal: Find a $n$-vector $x$, all of whose entries are 0 or 1, such that $Ax=1$, where $1$ denotes the all-ones vector

The ZOE problem is NP-complete. This is proven in Chapter 8.3 of Algorithms (Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani). The proof proceeds by reducing 3SAT to 3D Matching, and then reducing 3D Matching to ZOE.

Now we can reduce ZOE to #1, as follows. If we have an instance of ZOE $A$, we transform it as follows. For each variable $x_i$ of the ZOE instance, we add another variable $x^*_i$ and an equation $x_i + x^*_i = 1$. (This has the effect of forcing $x_i$ to be either 0 or 1, since we'll require $x_i \ge 0$ and $x^*_i \ge 0$ and $x_i,x^*_i$ are integers.) Thus, if the ZOE instance had a $m\times n$ matrix $A$, we now obtain $m+n$ equations in $2n$ unknowns, corresponding to some matrix $A'$. In other words, we obtain a problem instance $A'x' = b$ where $b=1$ is the all-ones vector, and where every entry of $A'$ is 0 or 1. This is now an instance of your problem #1. This instance of your problem #1 has a feasible solution if and only if the original ZOE instance has a feasible solution. This proves that any efficient algorithm to your #1 in turn yields an efficient algorithm for ZOE -- but since ZOE is NP-complete, it follows that #1 is NP-complete as well.

It follows from this result that #2, #3, and #4 are NP-complete as well, as #1 is a special case of them.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39992

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback