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


9

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

minf(x)s.t.Ax=bxi0ixi{0,1}i

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ą ( )?NPA,bf(x)f(x)=icixi


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

2
Odpowiedź na twoje pytanie brzmi: tak.

Odpowiedzi:


4

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.