Given a $0,1$ (binary) integer program of the form:

$$ \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \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 & 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$ )?


migrated from cstheory.stackexchange.com Feb 15 '13 at 16:05

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

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

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.


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.