Sea un conjunto de formas rectangulares -dimensionales. Para y , describe la longitud de en la dimensión . La misma notación se utiliza para el contenedor C . El problema del empaque ortogonal dimensional D (OPP- D ) es decidir si V encaja en el contenedor C sin solaparse. Formalmente, el problema consiste en averiguar si ∀ d ∈ { 1 , . . . , D d ∈ { 1 , . . . , D } v ∈ V w d ( v ) ∈ Q + v d existe una función f d : V → Q + , tal que ∀ v ∈ V , f d ( v ) + w d ( v ) ≤ w d ( C ) y ∀ v 1 , v 2 ∈ V , ( v 1 ≠ v 2 ) , [ f d ( v 1 ) , .
El problema es NP completo (ver Fekete SP, Schepers J. "Sobre el empaquetamiento de dimensiones superiores I: Modelado". Informe técnico 97–288, Universidad de zu Köln, 1997). El problema es NP-completo incluso para . Me pregunto si el problema del empaque ortogonal para un número limitado de tipos (es decir, tamaños en cada dimensión) de los ítems sigue siendo NP completo o no. Hasta ahora encontré un resultado en algún artículo sobre la integridad de NP de los cuadrados de empaque en un cuadrado (ver JOSEPH YT. LEUNG, TOMMY W. TAM, y CS WONG, "Empaque de cuadrados en un cuadrado", Journal of Parallel and Distributed Computing, Volumen 10, número 3, noviembre de 1990), que ya es una restricción, pero aún no sé qué sucede cuando se limita el número de tipos de elementos.
Gracias por su respuesta,
Respuestas:
Creo que el artículo de Klaus Jansen y Roberto Solis-Oba " Un algoritmo OPT + 1 para el problema del stock de corte con un número constante de longitudes de objeto " tiene una respuesta parcial a su pregunta. Consideran un caso especial de su problema conocido como Problema de corte de stock cuando el número de diferentes tipos de objetos es constante y se define de la siguiente manera:
Los autores afirman que
Y proponen un algoritmo de tiempo polinómico de aproximación cuando d es fijo.O PT+ 1 re
Como no se ha demostrado que este caso especial esté en , esta es la evidencia de que su problema es N P -duro.PAGS nortePAGS
Anexo: se sabe que el caso con dos tipos de objeto ( ) es polinomialmente solucionable, pero para d = 3 solo se conoce la aproximación O P T + 1 .re= 2 re= 3 O PT+ 1
fuente