Twardość NP specjalnego przypadku problemu upakowania ortogonalnego

Pozwolić $V$ być zestawem $D$-wymiarowe kształty prostokątne. Dla$d \in \{1,...,D\}$ i $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ opisuje długość $v$ w wymiarze $d$. Ta sama notacja jest używana dla kontenera$C$. The$D$-wymiarowy problem pakowania ortogonalnego (OPP-$D$) ma zdecydować, czy $V$ pasuje do pojemnika $C$bez nakładania się. Formalnie rzecz biorąc, problemem jest ustalenie, czy$\forall d \in \{1,...,D\}$ istnieje funkcja $f_d:V\rightarrow \mathbb{Q}^{+}$, takie że $\forall v \in V, f_d(v)+w_d(v) \leq w_d(C)$ i $\forall v_1,v_2 \in V$, $(v_1 \neq v_2)$, $[f_d(v_1),f_d(v_1)+w_d(v_1)) \cap [f_d(v_2),f_d(v_2)+w_d(v_2)) = \emptyset$.

Problem jest NP-zupełny (patrz Fekete SP, Schepers J. „O pakowaniu wielowymiarowym I: Modelowanie”. Raport techniczny 97–288, Uniwersytet w zu Köln, 1997). Problem jest NP-zupełny nawet dla$D=2$. Zastanawiam się, czy problem z ortogonalnym pakowaniem dla ograniczonej liczby rodzajów (tj. Rozmiarów w każdym wymiarze) przedmiotów jest nadal NP-zupełny, czy nie. Do tej pory znalazłem wynik w artykule na temat kompletności NP pakowania kwadratów w kwadrat (patrz JOSEPH YT. LEUNG, TOMMY W. TAM i CS WONG, „Pakowanie kwadratów w kwadrat”, Journal of Parallel and Distributed Computing, Tom 10, wydanie 3, listopad 1990), który jest już ograniczeniem, ale wciąż nie wiem, co się dzieje, gdy liczba rodzajów przedmiotów jest ograniczona.

Dziękuję za Twoją odpowiedź,

Myślę, że artykuł Klausa Jansena i Roberta Solis-Oby „ Algorytm OPT + 1 dla problemu zapasu ze stałą liczbą długości obiektów ” zawiera częściową odpowiedź na twoje pytanie. Biorą pod uwagę szczególny przypadek problemu znany jako problem zapasu skrawającego, gdy liczba różnych typów obiektów jest stała i zdefiniowana w następujący sposób:

W przypadku problemu z zapasem otrzymujemy zestaw$T = \{T_1,T_2,\dots,T_d\}$ typów obiektów, gdzie obiekty typu $T_i$ mają dodatnią długość całkowitą $p_i$. Biorąc pod uwagę nieskończony zestaw pojemników, każdy o pojemności całkowitej$\beta$, problemem jest spakowanie zestawu $\mathcal{O}$ z $n$sprzeciwia się minimalnej możliwej liczbie pojemników w taki sposób, aby pojemność pojemników nie została przekroczona; w komplecie$\mathcal{O}$ tam są $n_i$ obiekty typu $T_i$, dla wszystkich $i =1,\dots,d$.

Autorzy twierdzą, że

nie wiadomo, czy problem zapasu skrawającego można rozwiązać w czasie wielomianowym dla każdej stałej wartości $d$.

I proponują $OPT+1$ algorytm aproksymacji czasu wielomianowego, gdy $d$ jest naprawiony.

Ponieważ nie udowodniono, że ten wyjątkowy przypadek ma miejsce $P$, to dowód na to, że masz problem $NP$-ciężko.

Uzupełnienie: to wiadomo , że w przypadku dwóch typów obiektów ($d=2$) można rozwiązać wielomianowo, ale dla $d=3$ jest tylko znane $OPT+1$-przybliżenie.