Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$ )?

share|cite|improve this question

migrated from Feb 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
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.