Hardness of approximating 0-1 integer programs Given a $0,1$ (binary) integer program of the form:

$$
\begin{array}{lll}
\text{min} &amp; f(x) &amp; \\
\text{s.t.} &amp; A x = b \\
 &amp; x_i \ge 0 &amp; \quad \forall i\\
 &amp; x_i \in \{0,1\} &amp; \quad \forall i
\end{array}
$$

Note that 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) by Garey &amp; Johnson. If so, is this still the case when $A, b$ have binary entries and $f(x)$ is a linear function ( $f(x) = \sum_i c_i x_i$ )?
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.