In an effort to make my semesters easier, during breaks I do most of the research on the problems and write quick sketches of the reductions out. This way when I get to the weekly post, most of the hard math work is done, and I don’t get surprised by a super hard problem.

(I’m doing something similar over our winter break at the present. I’ve got sketches up through the middle of April, and I’m currently working on problem SR13- “Sparse Matrix Compression”- which is an “unpublished manuscript” problem that I’m having a lot of trouble with. Keep your fingers crossed).

Anyway, I was looking through my notes today and I realized that I’d skipped this problem! Luckily, I think the reduction is pretty easy.

**The problem: **Numerical Matching With Target Sums. This is problem SP17 in the appendix.

**The description: **Given two sets X and Y, each with the same number (m) of elements, and each with a positive integer size. We’re also given a “target vector” V, also of M elements, consisting of positive integer entities. Can we create m sets A_{1} through A_{m} such that:

- Each A
_{i}has one element from X and one element from Y - Each element in X and Y appears exactly once in some A
_{i} - The sum of the sizes of the elements in each A
_{i}is exactly B_{i}?

**Example: **I’ll use an example derived from last week’s Numerical 3-Dimensional Matching example because I think it will illustrate how the reduction will work:

- X = {12,11,7,5}
- Y = {1,1,4,5}
- B = {13,12,11,10}

(W from last week was {1,2,3,4}, and B was 14.)

Letting A_{1} be the first elements of X and Y, A_{2} being the second elements of X and Y, and so on down, gives us a solution.

**Reduction: **G&J say to use Numerical 3-Dimensional Matching, and don’t even bother to mark it as “unpublished results”, probably because they think it’s so easy.

Our Numerical 3DM instance is three sets: W, X, and Y, and a bound B. We need 2 sets and a “bound vector” for the instance of the Numerical Matching problem. So what we do is:

- X’ = X
- Y’ = Y
- Each b
_{i}in the B vector will be set to B-w_{i}. This is the amount we need the element from X and Y to add up to, so that when we add in the element from W, we get B.

If we have a solution to the Numerical 3-Dimensional Matching solution, then each A_{i} in that solution consists of 3 elements: w_{i}, x_{j }and y_{k} that sum to B. Then in our Numerical Matching With target Sums instance, we have a set A_{i}‘ where x_{j} + y_{k} sum to B-w_{i}. The same is true in the reverse direction.

**Difficulty: **3, which may be too high. I can see people getting confused by the fact that the sets in the 3DM instance can be taken in any order, but the B vector in the Target Sum matching problem needs to have A_{i}‘s element sum exactly to b_{i}, and wondering how to force the correct W element to be in that spot?

(The answer is that you define it when you build B. We set b_{1} to be “the sum that works when you use w_{i}“, so it (or something with the exact same size, so we can swap the elements) has to go in that position in the vector).