[+] 3partition I. 2partition vs. 3partition; variations (Subset Sum, Numerical 3dimensional matching, 3DM, X3C); weakly vs. strongly NPhard; pseudopolynomial vs. polynomial. Multiprocessor scheduling, rectangle packing, edgematching puzzles, jigsaw puzzles, polyform packing puzzles, packing squares into a square.  
This lecture introduces my favorite (and a generally lesser known)
starting point for NPhardness reductions, called 3partition.
This problem is particularly useful when you have a problem that involves
adding up numbers, even when those numbers must be encoded in unary (a common
feature of many puzzles). We'll discuss many variations of the problem:
2partition vs. 3partition is an example of the weak vs. strong NPhardness dichotomy, and on the algorithmic side, the pseudopolynomial vs. (weakly) polynomial dichotomy. We'll see weak and strong NPhardness proofs, by reductions from 2partition and 3partition respectively, for two problems:
Next we'll see a fun series of reductions between different puzzles, starting from 3partition / rectangle packing to establish strong NPhardness.
Finally, we'll see how to prove strong NPhardness of packing squares into a square. This is a handy result that we'll use as the basis for another reduction next lecture. 
Handwritten notes, page 1/10 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/10 • [previous page] • [next page] • [PDF] 

Slides, page 1/16 •
[previous page] •
[next page] •
[PDF]
Slides, page 1/16 • [previous page] • [next page] • [PDF] 