Three-Way Matching of Integers

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 {a1 .. an), and a set B with 2n integers (b1, b2n), can we split B into n pairs of elements, where each pair Pi={bj, bk}  and the sum of ai+bj+ bk = 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 = {}.  Then c will be 15, and P1 = {6,8}, P2 = {4,9}, P3 = {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 Pi 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 Pi 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.

Leave a Reply

Your email address will not be published. Required fields are marked *