Dureza de la aproximación de programas enteros 0-1

9

Dado un programa entero (binario) de la forma:0,1

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

Tenga en cuenta que el tamaño de no está fijo en ninguna de las dimensiones.A

Creo que Garey & Johnson ha demostrado que este problema es difícil de aproximar (fuertemente -Complete) . Si es así, ¿sigue siendo así cuando tienen entradas binarias es una función lineal ( )?NPA,bf(x)f(x)=icixi

Jonas Anderson
fuente
2
"Difícil de aproximar" y "fuertemente NP-completo" son dos nociones diferentes.
Tsuyoshi Ito
2
La respuesta a tu pregunta es sí.

Respuestas:

4

Uno de cada tres 3SAT es NP-completo. En cuanto a la reducción, hereda la dureza APX de 3SAT. Puede formular uno de cada tres 3SAT como un programa entero binario con entradas binarias, por lo que su problema es APX-hard.

Yuval Filmus
fuente