2
$\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 Answer 1

Reset to default
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$
2
  • $\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, 2019 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, 2019 at 15:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .