7
$\begingroup$

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following figure.

square-packing

In the $\textsf{3-Partition}$ instance, there are $n$ elements $(a_1, \cdots, a_i, \cdots, a_n)$. The target sum $t$ is $t = \frac{\sum a_i}{n/3}$.

In the reduction, $B$ is a huge (constant) number and each $a_i$ is represented by a $(B + a_i) \times (B + a_i)$ square. The blank in the rectangle will be filled by unit ($1 \times 1$) squares.


Questions: I don't quite understand the trick of "adding a huge number $B$" in the reduction. I guess it is used to force that any packing scheme will give a solution to $\textsf{3-Partition}$. But how?

Question 1: What is the trick of "adding a huge number" for in the reduction from $\textsf{3-Partition}$? Specifically, why does this reduction work? Why is this trick necessary, i.e., why wouldn't the reduction work if we left out $B$ (set $B=0$)?

I tried to identify the flaw of the proof of "any packing gives a 3-partition" but could not get the key point.

Actually I have also seen other reductions from $\textsf{3-Partition}$ that also use this trick. So,

Question 2: What is the general purpose of this trick of "adding a huge number" in the reductions from $\textsf{3-Partition}$ (if there is)?


Note: This problem is from the video lecture (from 01:15:15) by Prof. Erik Demaine. I should have first checked the original paper "Packing squares into a square". However, it is not accessible to me on the Internet. If you have a copy and would like to share, you can find my mailbox in my profile. Thanks in advance.

$\endgroup$
  • $\begingroup$ I haven't seen Demaine's proof, but you have a reduction from a similar problem here. $\endgroup$ – R B Jan 31 '15 at 10:46
  • $\begingroup$ What do you mean by "what is the trick of..."? Can you formulate Question 1 in a more specific way? Do you mean, why does this reduction work? Do you mean, why is this necessary, i.e., why wouldn't the reduction work if we left out $B$ (set $B=0$)? Something else? And, then once you've spelled it out, can you tell us what you tried to answer that question on your own? $\endgroup$ – D.W. Feb 1 '15 at 19:05
  • $\begingroup$ @D.W. Thanks for your suggestion. I have tried to find the flaw of the proof of "every packing gives a 3-partition" when $B = 0$. However I do not have the original proof and have difficulty in this. $\endgroup$ – hengxin Feb 2 '15 at 4:07
  • $\begingroup$ Do you mean you don't have the details of the reduction from 3-Partition to Packing Squares, only an outline of it? What do you mean by "the original proof"? As far as the paper that you can't find on the Internet: Have you tried visiting your local library to see if they can get you a copy of the paper you mention, or tried contacting the authors? $\endgroup$ – D.W. Feb 2 '15 at 4:20
  • $\begingroup$ @D.W. It is quite possible that I can find the answer from the proof in the paper (which is not accessible). The outline (the picture) proof misses too many details. Basically I want to find out why $B$ is necessary in the reduction. Maybe I can try to contact the authors. $\endgroup$ – hengxin Feb 2 '15 at 4:31
1
$\begingroup$

The large $B$ is here to ensure that the squares follow the pattern shown in the figure.

In the part "there exists a packing $\Rightarrow$ there exists a 3-partition". You need to exhibit tripples of integers with sum $=t$. This is easy if the coding squares in the packing are arranged 3-by-3 as in the picture, but how do you know this is the case? For instance, with very slightly smaller blue squares, you could have two small squares side by side in the same column, and then you'd be in trouble.

One way to use the trick of the $B$ constant is to say that it is not possible to have any horizontal line crossing strictly more than $n/3$ squares (such a line has length $(B+t)\frac n3$, a square has size at least $B$, and $B > t\frac n3$). So each horizontal line meets a 1st square, a 2nd square, etc., and then you can show (again using the large $B$), that the $i$th squares of each lines must all meet in the same column. Once you've got this, then you get a 3-partition.

About Question 2, it is obviously hard to give a formal answer, but the general pattern is the following:with 3-partition, you need to introduce some kind of slackness to allow that any integer in an interval $[min,max]$ can be somehow encoded and embeded in a slot (which must then correspond to the maximum possible size). But then a common issue is having two integers fitting in the same slot, or more generally other overlapping issues (as with the squares here). This is solved by making sure that the $min$ is large enough compared to the slot size (we often need $min > max/2$, or $min > max*(n-1)/(n)$ here): this is easily achieved with an additive constant $B$.

Edit Sample instance where $B$ is necessary: Let the instance of 3-partition be $(10,7,2,10,9,2)$ with $t=20$. This is a no-instance. However, with $B=0$, you have a valid packing of the $40\times 20$ rectangle: use a first column with four squares $(10,7,2,2)$, the last two being side-by-side, and a second column with only $(10,9)$. This is not possible with, say, $B=100$, and a $240 \times 320$ rectangle.

$\endgroup$

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.