NP-Dureza de un caso especial de problema de empaque ortogonal

9

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 , . . . , DV d { 1 , . . . , D } v V w d ( v ) Q + v drere{1,...,re}vVwre(v)Q+vreCDDVC existe una función f d : V Q + , tal quev V , f d ( v ) + w d ( v ) w d ( C ) yv 1 , v 2V , ( v 1v 2 ) , [ f d ( v 1 ) ,d{1,...,D}fd:VQ+vV,fd(v)+wd(v)wd(C)v1,v2V(v1v2) .[Fre(v1),Fre(v1)+wre(v1))[Fre(v2),Fre(v2)+wre(v2))=

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.D=2

Gracias por su respuesta,

Petru
fuente
3
¿Puedes indicar el problema original?
Suresh Venkat
¿Cuál es el problema de embalaje ortogonal?
Tsuyoshi Ito
2
(1) No soy un experto en el tema, pero ¿no es esa descripción del problema demasiado incompleta para analizar su complejidad? (2) Intente utilizar los comentarios de otras personas para mejorar su pregunta editándola, en lugar de agregar más comentarios. La mayoría de la gente no quiere seguir las discusiones en los comentarios solo para entender la pregunta.
Tsuyoshi Ito
2
Quizás intente definir rigurosamente cuál es el problema editando su pregunta (haga clic en el botón de edición anterior) y agregue algunas referencias que haya encontrado. Eso ayudará a la comunidad a comprender lo que ha sabido y lo que quiere saber. ¡Ayúdanos a ayudarte!
Hsien-Chih Chang 張顯 之
(Mi comentario y comentario de Hsien-Chih hace referencia al comentario anterior del autor de la pregunta dibujando lo que el problema de embalaje es ortogonal, que se ha suprimido más adelante.)
Tsuyoshi Ito

Respuestas:

7

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:

En el problema del material de corte , se nos da un conjunto de tipos de objetos, donde los objetos de tipoT={T1,T2,...,Tre} tienen positivo longitud número entero p i . Dado un conjunto infinito de contenedores, cada uno de capacidad entera β , el problema es empaquetar un conjunto O de n objetos en el mínimo número posible de contenedores de tal manera que no se exceda la capacidad de los contenedores; en el conjunto O hay n i objetos de tipo TTyopagsyoβOnorteOnorteyo , para todo i = 1 , ... , d .Tyoyo=1,...,re

Los autores afirman que

no se sabe si el problema del material de corte se puede resolver en tiempo polinómico para cada valor fijo .re

Y proponen un algoritmo de tiempo polinómico de aproximación cuando d es fijo.OPAGST+1re

Como no se ha demostrado que este caso especial esté en , esta es la evidencia de que su problema es N P -duro.PAGSnortePAGS

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=2re=3OPAGST+1

Oleksandr Bondarenko
fuente
Gracias por su respuesta. No se demostró que estuviera en , pero tampoco NP-hard ¿verdad? De todos modos, como dijiste, me da una respuesta parcial y me hace pensar que para OPP-2 probablemente no se estudió. PAGS
Petru
Creo que probablemente tengas razón en que tu problema no fue estudiado. Como dijiste "No se demostró que estuviera en P, pero tampoco NP-hard" y también lo entiendo de esta manera.
Oleksandr Bondarenko
2
Quizás este problema se pueda agregar a la lista de problemas "no se sabe que están en P o que son NPC".
Hsien-Chih Chang 張顯 之