Tag Archives: Partition

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.

Subset Product

I’m setting this to post automatically on the 27th.  Hopefully, it posts correctly.

Sp12 is Partition

Sp13 is Subset Sum

This next problem is related to those, but has a cool twist.

The problem: Subset Product.  This is problem SP14 in the appendix.

The description: Given a set A of positive integers, and a positive integer B, is there a subset A’ of A such that the product of the sizes all elements in A’ is exactly B?

(The G&J definition of the problem defines A as a set of generic elements, each with a positive integer “size”.  This is more general in that it allows for two different elements in A to have the same size.  But most of the time this and similar problems (for example: Subset Sum, Partition) are encountered, it is with the definition above)

Example: Let A = {1,2,3,4,5,6} .  If B = 60, then setting A’ to {2,4,5} solves the problem.  If B=61, then no subset of A will multiply to B.  61 is easy to see since it’s prime, but other non-prime numbers (like 35) also will not have a solution.

The reduction: G&J say to use X3C, and I’ll admit that this idea came to me while I was wrestling with the reductions for Comparative Containment and its relatives, with all of their work creating sets based on prime numbers.

We start with an instance of X3C: a set X with 3q elements, and a collection of 3-element subsets of X.

What we’re going to do is assign a prime number to each element in X- so the first 3q prime numbers will be allocated.

Each element in C will be represented by an element whose size is the product of the 3 prime numbers corresponding to the elements in C.   Notice that since each of the elements in X are represented by distinct prime numbers, the only way for two elements in C to generate the same number is if the two elements in C were exactly the same.  (In which case, the duplicate can be safely removed).

Our set A will be the collection of these C numbers, and our integer B will be the product of the first 3q primes.

So, if a cover C’ exists, multiplying all of the elements in C’ together will give us a number that is the product of the first 3q primes, because each element x in X will appear as a factor in some c in C’ exactly once, and thus each x’s prime number assignment will appear exactly once in the product of all of the numbers that represent the sets in C’.

If a subset A’ of A that multiplies to B exists, then the prime factorization of B gets us each of the first 3q prime numbers exactly once.  Each of the elements in A’ corresponds to a set in C, and the prime factorization of that element in A’ will “cover” three elements in X.  The union of all such coverings will cover X entirely.

The only hard part that remains is to decide whether we can actually find the first 3q prime numbers in polynomial time.  The prime number theorem says that the nth prime number is proportional to n log n, and brute-forcing whether a number is prime is O(\sqrt{n}).  Thus, we should be able to find the first 3q prime numbers in polynomial time just by checking each number individually, starting from 2.  Obviously, more efficient methods also exist.

Difficulty: 4.  It’s easy to go off in very different directions (for example, trying to compare this problem to Sum of Subsets by realizing that taking the logarithm of a product gets you a sum). Also the prime number theorem stuff isn’t obvious, and I don’t know how you mention its existence to students without spoiling the entire reduction.

Still, once they have that possibly obscure bit of knowledge, this is a good easy reduction that many students can follow.