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.

Thank you for your answer,

  • 3
    $\begingroup$ can you state the original problem ? $\endgroup$ Commented Dec 16, 2010 at 15:22
  • $\begingroup$ What is orthogonal packing problem? $\endgroup$ Commented Dec 16, 2010 at 15:23
  • 2
    $\begingroup$ (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. $\endgroup$ Commented Dec 16, 2010 at 15:46
  • 2
    $\begingroup$ 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! $\endgroup$ Commented Dec 16, 2010 at 15:48
  • $\begingroup$ (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.) $\endgroup$ Commented Dec 16, 2010 at 19:27

1 Answer 1


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 different 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 infinite 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 fixed 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.

  • $\begingroup$ 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. $\endgroup$
    – Petru
    Commented Dec 17, 2010 at 8:44
  • $\begingroup$ 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. $\endgroup$ Commented Dec 17, 2010 at 12:56
  • 2
    $\begingroup$ Maybe this problem can be added into the list of "not known to be in P or being NPC" problems. $\endgroup$ Commented Dec 17, 2010 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.