I am looking at the following solved exercise:

enter image description here

I haven't really understood at the reduction the part that we construct for each number $a_i$ a package of measurement $(\frac{4}{A}a_i, 5,3)$. Why do we consider this measurement?


closed as off-topic by Marzio De Biasi, Mohammad Al-Turkistany, Jan Johannsen, Yuval Filmus, Hsien-Chih Chang 張顯之 Jul 27 '16 at 19:00

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Marzio De Biasi, Mohammad Al-Turkistany, Jan Johannsen, Yuval Filmus, Hsien-Chih Chang 張顯之
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ (Incidentally, I don't see any way of showing membership in NP for that problem, so I also don't see any way of showing NP-completeness for that problem.) ​ ​ $\endgroup$ – user6973 Jul 27 '16 at 9:34
  • $\begingroup$ You are on the wrong site. Please read our help center. See also Computer Science which has a broader scope. $\endgroup$ – Kaveh Jul 28 '16 at 2:57

The packages are constructed in that way to turn the problem into a one-dimensional problem (Partition is one-dimensional). If all the packages have width 5 and height 3 (i.e. exactly the width and height of the truck), then the only dimension that matters is the length (the first coordinate) in order to make them fit because they fit exactly in the other two dimensions. The factor $\frac{4}{A}$ is just to make the sum of all the values exactly $4$ (twice the truck's length). That way the packages fit in the two trucks if and only if there is a partition of them into two sets of packages such that the total length of each set is exactly 2, which as argued in the solution is equivalent to have a partition for the original set of values $a_i$.

Notice that the largest dimensions are the ones fixed because that way there is only one feasible orientation for the packages (they cannot be rotated because they would not fit).

Hope it is clear. Best regards!

  • $\begingroup$ The normal problem with the packages is three-dimensional because we have $3$ unknown variables, $x_i, y_i, z_i$ and the partition problem is one-dimensional because we have just the value $a_i$ ? $\endgroup$ – Mary Star Jul 27 '16 at 9:53
  • $\begingroup$ Your last claim is wrong because you cannot easily show that rotating the packages cannot give a better fit. That is why we should use the largest dimensions of the truck, because it is easy to prove that the package must be placed in that one orientation only. $\endgroup$ – user21820 Jul 27 '16 at 10:25
  • $\begingroup$ @MaryStar: Those are not unknown; they are given. The unknown variables are the positions and rotations, $6$ for each package! $\endgroup$ – user21820 Jul 27 '16 at 10:34
  • 1
    $\begingroup$ @user21820 You are right, thanks. I edited the answer. $\endgroup$ – W. Gálvez Jul 27 '16 at 11:02
  • $\begingroup$ I haven't really understood why the largest dimensions have to be fixed. Could you explain it to me? $\endgroup$ – Mary Star Jul 28 '16 at 0:34

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