Kth Largest m-Tuple

I think I’m going to move the posts to Wednesday this semester since I teach two 2-hour classes on Tuesday/Thursday.

SP19 is Minimum Sum of Squares

SP20 is Kth Largest Subset and is very similar to our next problem.

The problem: Kth Largest m-Tuple.  This is problem SP21 in the appendix.

The description: Given sets X1 through Xm that all contain positive integers, and integers K and B, are there at least K m-tuples (x1, .., xm) from X1 x X2 x … x Xm for which the sum of the elements in each tuple is at least B?

Example: Let X1 = {1,2,3,4}, X2 = {5,10}, X3 = {1,2}. Notice that the X’s can be different sizes, and can repeat elements.

If B = 15, then the only tuples that sum to at least 15 are {3.10,2), (4,10,1), and  (4,10,2).

Reduction: The paper by Johnson and Mizoguchi presents the reduction pretty densely, but here is what I think they are saying:  We’re going to use a Turing Reduction to solve the Partition problem, which means we’re given an instance of Partition, and assume we can call a subroutine to solve the Kth Largest m-tuple problem multiple times to solve the Partition instance.  Recall that we can use Binary Search on multiple calls of the subroutine to determine (for example) how many tuples sum to some B or more.  (We need multiple calls because the subroutine is a boolean one, just saying yes or no to a given instance).

Updated reduction:

This idea came from Said D. in the comments, and I wanted to make sure it got posted here because it’s so simple and elegant.  If we are given a partition instance S = {s1..sn} and need to know if a subset sums to B (= half the sum of all of the elements in S), then the sets we create for the Kth Largest m-tuple instance are:

{s1+1, 1}, {s2+1, 1}, …(sn+1, 1}

And we number the K-th Largest m-tuple is looking for is B+n.  Each set will contribute 1 to the tuple sum no matter which element is chosen.  It may also contribute si as well, corresponding to whether we “take” that element in the partition instance or not.

That’s way better than what I was trying to do.  Thanks, Said!

The rest of my not very good reduction:

I’ll leave the rest up here for posterity, but this is way worse than Said’s idea above, and glosses over the fact that you can’t just use any elements you want as the sets- you need to set them up in a way that makes sure you don’t repeat elements when you choose the tuples.

So, in a manner similar to that used in the Kth Largest Subset reduction, we can find the number of tuples that sum to any B we want (including half the sum of all of the elements in the partition instance).  The only tricky part is that our “subsets” are tuples of different sizes.  So we need to run this algorithm multiple times:

  • Are there are 1-tuples that solve the partition problem?  (There are O(n)  1-tuples, so a binary search requires O(log n) calls)
  • Are there any 2 tuples that solve the partition problem?  (There are O(N^2) 2-tuples, so a binary search requires O(2* log n) calls)
  • Are there any m-tuples that solve the partition problem? (There are O(N!) n-tuples, so a binary search requires O(n * log n) calls)

Thus, we can do it in a polynomial number of calls to the K-th Largest m-tuple solver.

Difficulty: This is a little harder than the Kth largest subset reduction, which I gave a 5, so I’ll make this a 6.

5 responses to “Kth Largest m-Tuple

  1. How would you use the K-th Largest m-tuple oracle to decide if there is e.g. a 2-tuple to solve the partition problem?
    If you just set X_1=X_2 as the original partition instance you will also count numbers x such that x+x=2x=B/2 (i.e. it is allowed to sum some numbers multiple times to create one partition).

    From what I can see the paper reduces from subset sum with repetition where you do not have this problem and can apply straight-forward binary search.

  2. Yeah, you’re right, fixing it make this way more complicated than I want it to be.

    I was originally going to use integer knapsack (MP10), but convinced myself yesterday that since the G&J book says to use partition, that would work just as well.

    I’ll do integer knapsack next week so I can fix this. Thanks!

  3. Well, I think that you can do a simple reduction from partition but it is slightly different. If your partition instance is P=\{p_1,p_2,\ldots,p_k\} you could set X_1=\{1+p_1,1\}, X_2=\{1+p_2,1\}\ldots,X_k=\{1+p_k,1\} and look by binary search for tuples that sum to exactly B/2+k. Trivially these correspond to subsets of the partition instance that use disjoint elements and sum to B/2. If you allow non-negative numbers this reduction gets even easier.

  4. Thanks for the kind words, I am looking forward to the integer knapsack proof as I like that reduction.

Leave a Reply

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