NP-Dureza de um caso especial de problema de empacotamento ortogonal

9

Seja um conjunto de formas retangulares em D- dimensional. Para d { 1 , . . . , D } e v V , w d ( v ) Q + descreve o comprimento de v na dimensão d . A mesma notação é usada para o recipiente C . A D problema -dimensional ortogonal embalagem (OPP- D ) é decidir se V se encaixa no recipiente CVDd{1,...,D}vVwd(v)Q+vdCDDVCsem sobreposição. Formalmente, o problema é descobrir se existe uma função f d : V Q + , tal que v V , f d ( v ) + w d ( v ) w d ( C ) e v 1 , v 2Vd{1,...,D}fd:VQ+vV,fd(v)+wd(v)wd(C)v1,v2V, , [ f d ( v 1 ) , f d ( v 1 ) + w d ( v 1 ) ) [ f d ( v 2 ) , f d ( v 2 ) + w d ( v 2 ) ) = .(v1v2)[fd(v1),fd(v1)+wd(v1))[fd(v2),fd(v2)+wd(v2))=

O problema é NP-completo (veja Fekete SP, Schepers J. "Sobre embalagens com dimensões superiores I: Modelagem". Relatório Técnico 97–288, Universidade de zu Köln, 1997). O problema é NP-completo mesmo para . Gostaria de saber se o problema de empacotamento ortogonal para um número limitado de tipos (ou seja, tamanhos em cada dimensão) de itens ainda está completo ou não. Até agora, encontrei um resultado em algum artigo sobre a completude de NP de empacotar quadrados em um quadrado (consulte JOSEPH YT. LEUNG, TOMMY W. TAM e CS WONG, "Empacotar quadrados em um quadrado", Journal of Parallel and Distributed Distributed, Volume 10 Edição 3, novembro de 1990), que já é uma restrição, mas ainda não sei o que acontece quando o número de tipos de itens é limitado.D=2

Obrigado pela sua resposta,

Petru
fonte
3
você pode indicar o problema original?
Suresh Venkat
Qual é o problema de empacotamento ortogonal?
Tsuyoshi Ito
2
(1) Não sou especialista no assunto, mas a descrição do problema não é muito superficial para analisar sua complexidade? (2) Tente usar os comentários de outras pessoas para melhorar sua pergunta editando-a, em vez de adicionar mais comentários. A maioria das pessoas não deseja seguir as discussões nos comentários apenas para entender a pergunta.
Tsuyoshi Ito
2
Talvez tente definir rigorosamente qual é o problema editando sua pergunta (clique no botão editar acima) e adicione algumas referências encontradas. Isso ajudará a comunidade a entender o que você sabe e o que deseja saber. Ajude-nos a ajudá-lo!
Hsien-Chih Chang,
(Meu comentário e o comentário de Hsien-Chih se referiram ao comentário anterior do autor da pergunta, descrevendo qual é o problema de empacotamento ortogonal, que foi excluído mais tarde.)
Tsuyoshi Ito

Respostas:

7

Penso que o artigo de Klaus Jansen e Roberto Solis-Oba " Um algoritmo OPT + 1 para o problema do material de corte com número constante de comprimentos de objeto " tem uma resposta parcial à sua pergunta. Eles consideram um caso especial do seu problema conhecido como problema de estoque de corte quando o número de diferentes tipos de objetos é constante e definido da seguinte forma:

No problema do material de corte , recebemos um conjunto de tipos de objetos, onde objetos do tipo T i têm comprimento inteiro positivo p i . Dado um conjunto infinito de posições, cada uma com capacidade inteira β , o problema é empacotar um conjunto O de n objetos no número mínimo possível de posições, de modo que a capacidade das posições não seja excedida; no conjunto O existem n i objetos do tipo TT={T1,T2,,Td}TipiβOnOni , para todos i = 1 , , d .Tii=1,,d

Os autores afirmam que

não se sabe se o problema do material de corte pode ser resolvido em tempo polinomial para cada valor fixo .d

E eles propõem o algoritmo de tempo polinomial de aproximação quando d é fixo.OPT+1d

Uma vez que não está provado que este caso especial está em , esta é a evidência de que seu problema é N P -Hard.PNP

d=2d=3OPT+1

Oleksandr Bondarenko
fonte
P, but neither NP-hard right? Anyway, as you said it gives me a partial answer and makes me think that for OPP-2 it was most probably not studied.
Petru
I think you're probably right that your problem was not studied. As you said "It was not proved to be in P, but neither NP-hard" and I understand it this way too.
Oleksandr Bondarenko
2
Maybe this problem can be added into the list of "not known to be in P or being NPC" problems.
Hsien-Chih Chang 張顯之