# Hardness of Approximating 0-1 Integer Programs

Given a $0,1$ (binary) integer program of the form: $$\begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} &A\vec{x} = \vec{b} & \quad \forall i\\ &x_i\ge 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$ )?

-

## migrated from cstheory.stackexchange.comFeb 15 '13 at 16:05

This question came from our site for theoretical computer scientists and researchers in related fields.

“Hard to approximate” and “strongly NP-complete” are two different notions. – Tsuyoshi Ito Feb 14 '13 at 2:08
The answer to your question is yes. – Chandra Chekuri Feb 14 '13 at 19:35