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

9

Bei einem (binären) Ganzzahlprogramm der Form:0,1

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

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

Jonas Anderson
quelle
2
"Schwer zu approximieren" und "stark NP-vollständig" sind zwei verschiedene Begriffe.
Tsuyoshi Ito
2
Die Antwort auf Ihre Frage lautet ja.

Antworten:

4

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.

Yuval Filmus
quelle