10
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ “Hard to approximate” and “strongly NP-complete” are two different notions. $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 14, 2013 at 2:08
  • 2
    $\begingroup$ The answer to your question is yes. $\endgroup$
    – Chandra Chekuri
    Commented Feb 14, 2013 at 19:35
  • 1
    $\begingroup$ This problem, also called ZOP, is NPO-complete under strict reduction, as proved by Orponen and Mannila: users.ics.aalto.fi/orponen/papers/approx_1987.pdf . Strict reduction may have another name elsewhere as notations in computational optimization are not uniform across literature. $\endgroup$
    – plm
    Commented Apr 5 at 3:22

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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