NP-Hardness of a special case of orthogonal packing problem

Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used for the container $C$. The $D$-dimensional orthogonal packing problem (OPP-$D$) is to decide if $V$ fits into the container $C$ without overlapping. Formally speaking, the problem is to find out whether $\forall d \in \{1,...,D\}$ there exists a function $f_d:V\rightarrow \mathbb{Q}^{+}$, such that $\forall v \in V, f_d(v)+w_d(v) \leq w_d(C)$ and $\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$.

The problem is NP-complete (see Fekete SP, Schepers J. "On higher-dimensional packing I: Modeling". Technical Report 97–288, University at zu Köln, 1997). The problem is NP-complete even for $D=2$. I am wondering, whether the orthogonal packing problem for a bounded number of types (i.e. sizes in each dimension) of items is still NP-complete or not. Till now I found a result in some paper about NP-completeness of packing squares into a square (see JOSEPH Y-T. LEUNG, TOMMY W . TAM, AND C. S. WONG, "Packing squares into a square", Journal of Parallel and Distributed Computing, Volume 10 Issue 3, Nov. 1990) which is already a restriction but I still don't know what happens when the number of types of items is bounded.

• can you state the original problem ? – Suresh Venkat Dec 16 '10 at 15:22
• What is orthogonal packing problem? – Tsuyoshi Ito Dec 16 '10 at 15:23
• (1) I am not an expert on the subject, but isn’t that problem discription too sketchy to analyze its complexity? (2) Please try to use other people’s comments to improve your question by editing it, rather than adding more comments. Most people do not want to follow the discussions in comments just to understand the question. – Tsuyoshi Ito Dec 16 '10 at 15:46
• Maybe try to define rigorously what the problem is by editing your question (click the edit button above), and add some references you've found. That will help the community understand what you have known, and what do you want to know. Help us to help you! – Hsien-Chih Chang 張顯之 Dec 16 '10 at 15:48
• (My comment and Hsien-Chih’s comment referred to the asker’s earlier comment sketching what the orthogonal packing problem is, which has been deleted later.) – Tsuyoshi Ito Dec 16 '10 at 19:27

I think that the paper by Klaus Jansen and Roberto Solis-Oba "An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths" has a partial answer to your question. They consider a special case of your problem known as Cutting Stock problem when the number of diﬀerent object types is constant and defined as follows:

In the cutting stock problem we are given a set $T = \{T_1,T_2,\dots,T_d\}$ of object types, where objects of type $T_i$ have positive integer length $p_i$. Given an inﬁnite set of bins, each of integer capacity $\beta$, the problem is to pack a set $\mathcal{O}$ of $n$ objects into the minimum possible number of bins in such a way that the capacity of the bins is not exceeded; in set $\mathcal{O}$ there are $n_i$ objects of type $T_i$, for all $i =1,\dots,d$.

The authors claim that

it is not known whether the cutting stock problem can be solved in polynomial time for every ﬁxed value $d$.

And they propose $OPT+1$ approximation polynomial-time algorithm when $d$ is fixed.

Since it's not proved that this special case is in $P$, this is the evidence that your problem is $NP$-hard.

Addendum: it's known that the case with two object types ($d=2$) is polynomially solvable, but for $d=3$ there is known only $OPT+1$-approximation.

• Thank you for your answer. It was not proved to be in $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 Dec 17 '10 at 8:44
• 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 Dec 17 '10 at 12:56
• Maybe this problem can be added into the list of "not known to be in P or being NPC" problems. – Hsien-Chih Chang 張顯之 Dec 17 '10 at 16:23