1
$\begingroup$

I want to pack a number of rectangles into a larger rectangle, however, unlike other questions that I could find, I would like to do so exactly, without allowing any wastage. I do not really care whether 90° rotation is allowed, or not.

I find it hard to construct a reduction from the 2D-bin-packing problem to this problem, since this very special, restricted case of fitting the rectangles exactly might be more easy to decide after all. Any other reductions or proofs that I could find lead me to the same doubts. I also failed to construct a correct reduction from the 2d-knapsack problem with a similar argument.

My stomach tells me that this simplified problem is still NP-complete, but I was not able to find any proofs and I would be happy to be pointed to the correct direction. Additionally, if the constraint is changed so that only equal sized smaller rectangles allowed, is the problem still NP-complete?

$\endgroup$
1
$\begingroup$

Partition can be reduced to this problem. Set $S$ can be partitioned iff set of rectangles $\{1 \times (4\cdot x)| x \in S\}$ can be packed into rectangle $2 \times (\sum_{x \in S} 2x)$: rectangles from upper row corresponds to one subset, from bottom to other, and multiplication by $4$ ensures all rectangles are placed horizontally.

$\endgroup$
  • $\begingroup$ Ah, yes that would work! Thank you! That would also mean that the original problem is not strongly NP-hard, right? $\endgroup$ – Markus May 23 at 11:18
  • $\begingroup$ Of course this prove doesn't imply the original problem is not strongly NP hard (I don't know how to reduce it back to partition or any weakly NP complete problem). I suspect it is actually strongly NP hard, but have little evidence to say to confirm this suspicion. $\endgroup$ – mihaild May 23 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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