NP-Härte eines Sonderfalls eines orthogonalen Packungsproblems

9

Sei eine Menge von dimensionalen rechteckigen Formen. Für und , beschreibt die Länge von in der Dimension . Die gleiche Notation wird für den Container . Das dimensionale orthogonale Packungsproblem (OPP- ) besteht darin, zu entscheiden, ob ohne Überlappung in den Behälter passt . Formal besteht das Problem darin, herauszufinden, ob eine Funktion , so dassV.D.d{1,...,D.}}vV.wd(v)Q.+vdC.D.D.C d { 1 , . . . , D } f d : V Q +v V , f d ( v ) + w d ( v ) w d ( C )V.C.d{1,...,D.}}fd::V.Q.+vV.,fd(v)+wd(v)wd(C.) und , , .( v 1v 2 ) [ f d ( v 1 ) , f d ( v 1 ) + w d ( v 1 ) ) [ f d ( v 2 ) , f d ( v 2 ) + w d ( v 2 ) ) =v1,v2V.(v1v2)[fd(v1),fd(v1)+wd(v1))[fd(v2),fd(v2)+wd(v2))=

Das Problem ist NP-vollständig (siehe Fekete SP, Schepers J. "Über höherdimensionale Packung I: Modellierung". Technischer Bericht 97–288, Universität zu Köln, 1997). Das Problem ist auch für NP-vollständig . Ich frage mich, ob das orthogonale Packungsproblem für eine begrenzte Anzahl von Arten (dh Größen in jeder Dimension) von Gegenständen immer noch NP-vollständig ist oder nicht. Bis jetzt fand ich ein Ergebnis in einem Artikel über die NP-Vollständigkeit des Packens von Quadraten in ein Quadrat (siehe JOSEPH YT. LEUNG, TOMMY W. TAM UND CS WONG, "Packen von Quadraten in ein Quadrat", Journal of Parallel and Distributed Computing, Band 10, Ausgabe 3, November 1990), die bereits eine Einschränkung darstellt, aber ich weiß immer noch nicht, was passiert, wenn die Anzahl der Arten von Elementen begrenzt ist.D.=2

Vielen Dank für Ihre Antwort,

Petru
quelle
3
Können Sie das ursprüngliche Problem angeben?
Suresh Venkat
Was ist ein orthogonales Packungsproblem?
Tsuyoshi Ito
2
(1) Ich bin kein Experte auf diesem Gebiet, aber ist diese Problembeschreibung nicht zu lückenhaft, um ihre Komplexität zu analysieren? (2) Bitte versuchen Sie, die Kommentare anderer Personen zu verwenden, um Ihre Frage zu verbessern, indem Sie sie bearbeiten, anstatt weitere Kommentare hinzuzufügen. Die meisten Menschen möchten die Diskussionen nicht in Kommentaren verfolgen, nur um die Frage zu verstehen.
Tsuyoshi Ito
2
Versuchen Sie möglicherweise, das Problem genau zu definieren, indem Sie Ihre Frage bearbeiten (klicken Sie oben auf die Schaltfläche Bearbeiten), und fügen Sie einige gefundene Referenzen hinzu. Das hilft der Community zu verstehen, was Sie gewusst haben und was Sie wissen möchten. Helfen Sie uns, Ihnen zu helfen!
Hsien-Chih Chang 16 之
(Mein Kommentar und der Kommentar von Hsien-Chih bezogen sich auf den früheren Kommentar des Fragestellers, in dem das orthogonale Packungsproblem skizziert wurde, das später gelöscht wurde.)
Tsuyoshi Ito

Antworten:

7

Ich denke, dass das Papier von Klaus Jansen und Roberto Solis-Oba " Ein OPT + 1-Algorithmus für das Schneidmaterialproblem mit konstanter Anzahl von Objektlängen " eine teilweise Antwort auf Ihre Frage hat. Sie betrachten einen Sonderfall Ihres Problems, der als Schneidmaterialproblem bezeichnet wird, wenn die Anzahl der verschiedenen Objekttypen konstant und wie folgt definiert ist:

In dem Schneidmaterialproblem erhalten wir eine Menge von Objekttypen, wobei Objekte vom Typ eine positive ganzzahlige Länge . Bei einer unendlichen Menge von Bins mit jeweils ganzzahliger Kapazität besteht das Problem darin, eine Menge von Objekten so in die minimal mögliche Anzahl von Bins zu packen , dass die Kapazität der Bins nicht überschritten wird. In set gibt es Objekte vom Typ für alle .T i p i β O n O n i T i i = 1 , , dT.={T.1,T.2,,T.d}}T.ichpichβÖnÖnichT.ichich=1,,d

Die Autoren behaupten das

Es ist nicht bekannt, ob das Schneidmaterialproblem in Polynomzeit für jeden festen Wert gelöst werden kann .d

Und sie schlagen einen Approximationspolynom-Zeitalgorithmus vor, wenn fest ist.dÖP.T.+1d

Da es nicht bewiesen ist , dass dieser Sonderfall ist , dann ist dies der Beweis , dass Ihr Problem ist N P -hard.P.N.P.

Nachtrag: Es ist bekannt, dass der Fall mit zwei Objekttypen ( ) polynomiell lösbar ist, aber für d = 3 ist nur die O P T + 1- Approximation bekannt.d=2d=3ÖP.T.+1

Oleksandr Bondarenko
quelle
Vielen Dank für Ihre Antwort. Es wurde nicht nachgewiesen, dass es in , aber auch nicht NP-hart, oder? Wie Sie sagten, gibt es mir eine teilweise Antwort und lässt mich denken, dass es für OPP-2 höchstwahrscheinlich nicht untersucht wurde. P.
Petru
Ich denke, Sie haben wahrscheinlich Recht, dass Ihr Problem nicht untersucht wurde. Wie Sie sagten "Es wurde nicht bewiesen, dass es in P ist, aber auch nicht NP-hart" und ich verstehe es auch so.
Oleksandr Bondarenko
2
Möglicherweise kann dieses Problem in die Liste der Probleme "Nicht bekannt, dass es sich in P befindet oder NPC ist" aufgenommen werden.
Hsien-Chih Chang 17 之