Numerical Matching With Target Sums

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 A1 through Am such that:

  • Each Ai has one element from X and one element from Y
  • Each element in X and Y appears exactly once in some Ai
  • The sum of the sizes of the elements in each Ai is exactly Bi?

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 A1 be the first elements of X and Y, A2 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 bi in the B vector will be set to B-wi.  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 Ai in that solution consists of 3 elements: wi, xj and yk that sum to B.  Then in our Numerical Matching With target Sums instance, we have a set Ai‘ where xj + yk sum to B-wi.  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 Ai‘s element sum exactly to bi, 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 b1 to be “the sum that works when you use wi“, so it (or something with the exact same size, so we can swap the elements) has to go in that position in the vector).

Leave a Reply

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