NP-Dureté d'un cas particulier de problème de tassement orthogonal

9

Soit un ensemble de formes rectangulaires à dimensionsPour et , décrit la longueur de dans la dimension . La même notation est utilisée pour le conteneur . Le problème d' emballage de dimension orthogonale (Opp- ) est de décider si se insère dans le récipient sans se chevaucher. Formellement parlant, le problème est de savoir si existe une fonction , telle queD d { 1 , . . . , D } v V w d ( v ) Q + v d C D D V C j { 1 , . . . , D } f d : V Q +v V , f d ( v ) +VDd{1,...,D}vVwd(v)Q+vdCDDVCd{1,...,D}fd:VQ+v 1 , v 2V ( v 1v 2 ) [ f d ( v 1 ) , f d ( v 1 ) + w d ( v 1 ) ) [ f d ( v 2 ) , f d ( vvV,fd(v)+wd(v)wd(C) et , , .v1,v2V(v1v2)[fd(v1),fd(v1)+wd(v1))[fd(v2),fd(v2)+wd(v2))=

Le problème est NP-complet (voir Fekete SP, Schepers J. "Sur les emballages de dimension supérieure I: Modélisation". Rapport technique 97-288, Université de zu Köln, 1997). Le problème est NP-complet même pour . Je me demande si le problème d'emballage orthogonal pour un nombre limité de types (c'est-à-dire de tailles dans chaque dimension) d'articles est toujours NP-complet ou non. Jusqu'à présent, j'ai trouvé un résultat dans certains articles sur le caractère NP complet des carrés d'emballage dans un carré (voir JOSEPH YT. LEUNG, TOMMY W. TAM ET CS WONG, "Packing squares into a square", Journal of Parallel and Distributed Computing, Volume 10, numéro 3, novembre 1990), qui est déjà une restriction, mais je ne sais toujours pas ce qui se passe lorsque le nombre de types d'articles est limité.D=2

Merci pour votre réponse,

Petru
la source
3
pouvez-vous indiquer le problème d'origine?
Suresh Venkat
Quel est le problème d'emballage orthogonal?
Tsuyoshi Ito
2
(1) Je ne suis pas un expert en la matière, mais ce problème de description n'est-il pas trop sommaire pour analyser sa complexité? (2) Veuillez essayer d'utiliser les commentaires d'autres personnes pour améliorer votre question en la modifiant, plutôt qu'en ajoutant d'autres commentaires. La plupart des gens ne veulent pas suivre les discussions dans les commentaires juste pour comprendre la question.
Tsuyoshi Ito
2
Essayez peut-être de définir rigoureusement le problème en modifiant votre question (cliquez sur le bouton Modifier ci-dessus) et en ajoutant quelques références que vous avez trouvées. Cela aidera la communauté à comprendre ce que vous savez et ce que vous voulez savoir. Aidez nous à vous aider!
Hsien-Chih Chang 張顯 之
(Mon commentaire et le commentaire de Hsien-Chih se référaient au commentaire précédent du demandeur esquissant quel est le problème d'emballage orthogonal, qui a été supprimé plus tard.)
Tsuyoshi Ito

Réponses:

7

Je pense que l'article de Klaus Jansen et Roberto Solis-Oba " Un algorithme OPT + 1 pour le problème du stock de coupe avec un nombre constant de longueurs d'objet " a une réponse partielle à votre question. Ils considèrent un cas spécial de votre problème connu sous le nom de problème de stock de coupe lorsque le nombre de types d'objet différents est constant et défini comme suit:

Dans le problème du stock de coupe, on nous donne un ensemble de types d'objets, où les objets de type ont une longueur entière positive . Etant donné un ensemble infini de casiers, chacun de capacité entière , le problème est d'emballer un ensemble de objets dans le nombre minimum possible de casiers de telle sorte que la capacité des casiers ne soit pas dépassée; dans l'ensemble il y a objets de type , pour tout .T i p i β O n O n i T i i = 1 , , dT={T1,T2,,Td}TipiβOnOniTii=1,,d

Les auteurs affirment que

on ne sait pas si le problème du stock de coupe peut être résolu en temps polynomial pour chaque valeur fi xe .d

Et ils proposent l' algorithme de temps polynomial d'approximation lorsque est fixe.dOPT+1d

Comme il n'est pas prouvé que ce cas spécial est en , c'est la preuve que votre problème est dur.N PPNP

Addendum: il est connu que le cas avec deux types d'objets ( ) est solvable polynomialement, mais pour il n'y a qu'une approximation connue .d = 3 O P T + 1d=2d=3OPT+1

Oleksandr Bondarenko
la source
Merci pour votre réponse. Il ne s'est pas avéré être en , mais ni NP-hard non? Quoi qu'il en soit, comme vous l'avez dit, cela me donne une réponse partielle et me fait penser que pour OPP-2, il n'a probablement pas été étudié. P
Petru
Je pense que vous avez probablement raison de dire que votre problème n'a pas été étudié. Comme vous l'avez dit "Il n'a pas été prouvé qu'il était en P, mais ni NP-dur" et je le comprends aussi de cette façon.
Oleksandr Bondarenko
2
Peut-être que ce problème peut être ajouté à la liste des problèmes "inconnus pour être en P ou étant NPC".
Hsien-Chih Chang 張顯 之