Трудность аппроксимации 0-1 целочисленных программ

Дана (двоичная) целочисленная программа вида:$0,1$

$$\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}$$

Обратите внимание, что размер не фиксирован ни в одном измерении.$A$

Я полагаю, что эту проблему трудно доказать (сильно -завершено) Гэри и Джонсон . Если да, то это по- прежнему тот случай , когда , б есть двоичные входы и ф ( х ) является линейной функцией ( F ( х ) = Σ я с я х я )?${\sf NP}$$A, b$$f(x)$$f(x) = \sum_i c_i x_i$

Каждый третий 3SAT является NP-полным. Глядя на сокращение, он наследует APX-твердость 3SAT. Вы можете сформулировать один из трех 3SAT как двоичную целочисленную программу с двоичными записями, так что ваша проблема сложна для APX.