Härte der Annäherung an 0-1 Ganzzahlprogramme

Bei einem (binären) Ganzzahlprogramm der Form:$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}$$

Beachten Sie, dass die Größe von in keiner der Dimensionen festgelegt ist.$A$

Ich glaube, dass Garey & Johnson gezeigt haben, dass dieses Problem schwer zu approximieren ist (stark -Vollständig) . Wenn ja, ist dies immer noch der Fall, wenn binäre Einträge haben und eine lineare Funktion ist ( )?${\sf NP}$$A, b$$f(x)$$f(x) = \sum_i c_i x_i$

Jeder dritte 3SAT ist NP-vollständig. Betrachtet man die Reduzierung, so erbt es die APX-Härte von 3SAT. Sie können eins zu drei 3SAT als binäres Ganzzahlprogramm mit binären Einträgen formulieren, sodass Ihr Problem APX-schwer ist.