Problem Detail: Given a $0,1$ (binary) integer program of the form: $$ begin{array}{lll} text{min} & f(x) & text{s.t.} &Avec{x} = vec{b} & quad forall i &x_ige 0 & quad forall i &x_i in {0,1} & quad forall i end{array} $$ Note: the size of $A$ is not fixed in either dimension. I believe this problem has been shown to be hard to approximate (strongly ${sf NP}$-Complete) Garey & Johnson. If so, is this still the case when $A$, $vec{b}$ have binary entries and $f(x)$ is a linear function ( $f(x) = sum_i c_i x_i$ )?
Asked By : Jonas Anderson
Answered By : Yuval Filmus
One-in-three 3SAT is NP-complete. Looking at the reduction, it inherits the APX-hardness of 3SAT. You can formulate one-in-three 3SAT as a binary integer program with binary entries, so you problem is APX-hard.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9810 3.2K people like this
