Kekerasan mendekati 0-1 program integer

Diberikan program integer (biner) dari formulir:$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}$$

Perhatikan bahwa ukuran tidak tetap dalam dimensi mana pun.$A$

Saya percaya masalah ini telah terbukti sulit untuk diperkirakan (sangat -Lengkap) oleh Garey & Johnson . Jika demikian, apakah ini masih terjadi ketika A , b memiliki entri biner dan f ( x ) adalah fungsi linear ( f ( x ) = Σ i c i x i )?${\sf NP}$$A, b$$f(x)$$f(x) = \sum_i c_i x_i$

3SAT satu-dalam-tiga adalah NP-lengkap. Melihat pengurangan, itu mewarisi kekerasan APX dari 3SAT. Anda dapat memformulasikan 3SAT satu-dalam-tiga sebagai program integer biner dengan entri biner, sehingga masalah Anda adalah APX-hard.