This is an interesting variant on the Three-Dimensional Matching problem that will be used in the next reduction. Since I think it would make a good easy homework problem, I’m posting it mainly as a reminder to myself to use it.

**The problem: **Three-Way Matching of Integers. This problem isn’t in the appendix, but the paper by Papadimitriou and Kanellakis that describes it refers to G&J for the reduction. I think that it’s because it’s seen as a “trivial” extension of Numerical Three-Dimensional Matching.

**The description: **Given a set A with n integers {a_{1} .. a_{n}), and a set B with 2n integers (b_{1}, b_{2n}), can we split B into n pairs of elements, where each pair P_{i}={b_{j}, b_{k}} and the sum of a_{i}+b_{j}+ b_{k} = the same constant c for all i? (Notice that c will be 1/n of the sum of all of the elements in A and B)

**Example: ** I think the problem is simpler than the description. Suppose A = {1,2,3}, and B = {4.5.6.7.8.9}. Then c will be 15, and P_{1} = {6,8}, P_{2} = {4,9}, P_{3} = {5,7}.

**Reduction: **This is very close to Numerical Three-Dimensional Matching, so we’ll start there. So we’re given 3 sets X, Y, and Z, with n elements, and a bound B. We can assume that B = 1/n of the sum of all of the elements in X, Y, and Z.

We can’t just set A=X, and B= Y∪Z, because we need to make sure that a solution to our problem doesn’t build a P_{i} that takes 2 elements from Y (or Z). The fix is to add B to all of the elements of Y before putting them in B. So now c will be 2B (the old B that a triple adds to, plus the B we added to the element from Y that we need). This guarantees that each P_{i} will take one element that came from Y, and one element that came from Z.

**Difficulty: **3. I don’t think this is trivial since we have to change the original problem a bit in our reduction, but I think it is a change that’s not hard for people to figure out. Though you might convince me this should be a 2 instead.