Twardość zbliżonych programów całkowitych 0-1

Biorąc pod uwagę (binarny) program liczbowy w postaci:$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}$$

Zauważ, że rozmiar nie jest ustalony w żadnym z wymiarów.$A$

Uważam, że problem ten został trudny do oszacowania (zdecydowanie -Complete) przez Garey & Johnson . Jeśli tak, to czy nadal tak jest, gdy mają wpisy binarne, a jest funkcją liniową ( )?${\sf NP}$$A, b$$f(x)$$f(x) = \sum_i c_i x_i$

Jeden na trzech 3SAT jest kompletny z NP. Patrząc na redukcję, dziedziczy ona twardość APX 3SAT. Możesz sformułować 3SAT jeden na trzy jako binarny program z liczbami binarnymi, więc problem jest trudny w APX.