reference-request – Mochila multidimensional STRONGLY NP-complete

Pregunta:

¿Quién puede señalarme una referencia en la que se muestre realmente que la mochila multidimensional es fuertemente NP-completa ? He encontrado montones de papeles donde dicen que está, sin citación; Encontré otra carga donde citan a Garey & Johnson, aunque no está en su lista de problemas fuertemente NP-completos (Sec. 4.2); muchos citan a Garey & Johnson como "Una introducción a" en lugar de "Una guía para", por lo que estos autores probablemente se copiaron unos de otros. De hecho, algunos autores afirman que no es fuertemente NP-completo, un ejemplo es "El problema multidimensional 0-1 mochila: Una visión general" por Freville, pero el argumento (generalizar el DP para la mochila de una sola dimensión) es obviamente falsa, vea abajo.

La mochila multidimensional intenta maximizar $ \ sum_j c_j x_j $ de manera que $ \ sum_j a_ {ij} x_j \ le b_j $ para $ i = 1, …, m $, siendo $ x_i $ entero $ \ ge 0 $ ( y todos $ c_j, a_ {ij}, b_j $ siendo $ \ ge 0 $). También podemos exigir $ x_i \ in \ {0,1 \} $, la versión 0/1 del problema. Me alegraría que una prueba de que cualquiera de los dos sea difícil (la dureza del otro debería seguir fácilmente).

Fuertemente NP-hard se aplica solo a problemas numéricos y restringe el (algunos) máximo de números para que sean polinomiales en el tamaño de la instancia del problema (bits necesarios para codificarlo). Enérgicamente NP-hard descarta la existencia de un algoritmo pseudopolinomial para el problema, con polinomio de tiempo de ejecución en los números que aparecen en la instancia. La mochila habitual (unidimensional) tiene obviamente un algoritmo pseudopolinomial (DP), pero este algoritmo no se puede generalizar a KP multidimensional, ya que la dimensión del KP aparece en el exponente del tiempo de ejecución. Espero no haber estropeado nada en mis definiciones …

Respuesta:

En el artículo titulado "SOBRE PROBLEMAS DE EMBALAJE MULTIDIMENSIONAL" que apareció en SODA y luego en SICOMP ( http://epubs.siam.org/doi/abs/10.1137/S0097539799356265 ) consideramos varios problemas de empaque donde los artículos son vectores d-dimensionales. Discutimos PIP que son lo mismo que una mochila multidimensional (mencionamos esto) y su aproximabilidad cuando d no es fijo. Puede encontrar resultados de dureza en función de d en ese papel.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım