1
$\begingroup$

I was trying to solve problem from Cormen page 1100 34.5-2

Given an integer $m * n$ matrix A and an integer $m$-vector $b$, the 0-1 integer- programming problem asks whether there exists an integer $n$-vector $x$ with elements in the set $<0, 1>$ such that $Ax\leq b$. Prove that 0-1 integer programming is NP-complete. (Hint: Reduce from 3-CNF-SAT.)

I do not understand what is 0-1 integer programming problem and what m and n vector mean here... Like what $Ax\leq b$ means.

Here is solution (I will really appreciate if you can explain me this one..): enter image description here

$\endgroup$
1
$\begingroup$

Your $k$-vectors are just vectors with $k$ elements. The IntProg problem is defined by $$(A,b) \in \mathrm{IntProg} \\ \Leftrightarrow \exists x\in \{0,1\}^n : (Ax)_i \le b_i \forall 1\le i \le m$$ Where $A\in \mathbb R^{m\times n}$ and $b\in\mathbb R^m$. The RHS of the condition is abbreviated to $Ax \le b$ wich is to be read as "component-wise less than or equal to".

Intuitively IntProg asks if there is a subset of the columns of $A$ such that their sum ($Ax$ sums all the $i$-th columns where $x_i = 1$) is component-wise less than or equal to $b$.
For example $A = (3\ -1\ 2)$ and $b=-1$ is a yes-instance because the choice $x = (0\ 1\ 0)^T$ gives $Ax = -1 \le b$.

If you want to know what a vector and a matrix is, you should consult wikipedia or google.

$\endgroup$
11
  • $\begingroup$ I know what vector and matrix is.. but I am still totally unclear with the solution... $\endgroup$
    – YohanRoth
    Apr 22 '15 at 17:52
  • $\begingroup$ Can you ask a precise question? The only question in the original post asks about the meaning of the notation, wich I explained. $\endgroup$
    – AlexR
    Apr 22 '15 at 17:56
  • $\begingroup$ I am still not clear what is 0-1 integer-programming problem... I cannot make much sense from your pure math explanation. maybe you can add more words to it? $\endgroup$
    – YohanRoth
    Apr 22 '15 at 18:01
  • $\begingroup$ @PTNPNX I tried. Is this going into the right direction? Always keep in mind that $x_i \in \{0,1\}$ - that's a very important restriction. $\endgroup$
    – AlexR
    Apr 22 '15 at 18:06
  • $\begingroup$ so b can have any integer right? Not only 1, 0? And we want to know if there is n-vector x such that if we multiply matrix A with vector x we get resulting vector Ax which is pairwise smaller than b ? $\endgroup$
    – YohanRoth
    Apr 22 '15 at 18:14

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.