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

Biorąc pod uwagę (binarny) program liczbowy w postaci: $0,1$

\begin{array}{lll} min & f (x) \\ s.t. & A x = b \\ x_{i} \geq 0 & \forall i \\ x_{i} \in {0, 1} & \forall i \end{array}

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

— Jonas Anderson
źródło

„Trudne do przybliżenia” i „zdecydowanie NP-zupełne” to dwa różne pojęcia.

— Tsuyoshi Ito

Odpowiedź na twoje pytanie brzmi: tak.

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.

— Yuval Filmus
źródło