Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm given 3 multisets $A$, $B$, and $C$ each with $n$ elements. Now I'm to form $n$ (say $D_1$ to $D_n$) multisets of 3 elements each from $A$, $B$, and $C$, such that each of these $n$ multisets contain an element each from $A$, $B$, and $C$. My aim is to reduce the sum of products of elements in $D_i$; that is, I'll take the product of elements in each $D_i$, and take the sum of these. This summation is to be minimized. Brute forcing seems to be a pretty bad idea here because even for $n>5$, the algorithm slows down pretty badly. Any better ideas? Maybe using linear programming?

share|improve this question
    
Sets where elements can be repeated are called multisets. Can $A$, $B$, and $C$ have elements in common? If so, then the $D_i$ may also be multisets (if I've understood the question correctly). Please check that I have not accidentally altered the meaning of your question. –  Zev Chonoles Jun 3 '12 at 6:06
    
Yes Di can also be a mutiset . Thanks for the reformatting the text . Is there a tool somewhere in the formatting so that i can use mathematical equations and use sigma expression to represent the problem , That wud make it easier to understand the problem –  Malice Jun 3 '12 at 7:10
    
For equation editing, you could see meta.math.stackexchange.com/questions/1773/… to get started. –  Ross Millikan Jun 3 '12 at 7:44
add comment

2 Answers 2

up vote 0 down vote accepted

I assume that the elements of A, B, and C are positive integers given in binary. Then the problem is NP-hard. More precisely, the following decision problem is NP-complete:

Instance: Multisets A, B, and C each of which consists of n positive integers, and a positive integer K, all given in binary.
Question: Do there exist n triples (a1, b1, c1), …, (an, bn, cn) ∈ A×B×C such that A = {a1, …, an}, B = {b1, …, bn}, C = {c1, …, cn}, and $\sum_{i=1}^n a_ib_ic_i \le K$?

The membership to NP is clear. To prove NP-hardness, we reduce the numerical 3-dimensional matching problem (N3DM) to the current problem. It is known that N3DM is strongly NP-complete, or in other words, the following problem is NP-complete:

Instance: Multisets A, B, and C each of which consists of n positive integers, and a positive integer S such that $\sum_{a\in A}a+\sum_{b\in B}b+\sum_{c\in C}c=nS$, all given in unary.
Question: Do there exist n triples (a1, b1, c1), …, (an, bn, cn) ∈ A×B×C such that A = {a1, …, an}, B = {b1, …, bn}, C = {c1, …, cn}, and ai + bi + ci = S for all i?

Given an instance (A, B, C, S) of N3DM, construct multisets A′ = {2a: aA}, B′ = {2b: bB}, and C′ = {2c: cC}, and let K = n⋅2S. Then it is easy to see that the answer to the instance (A, B, C, S) of N3DM is “yes” if and only if the answer to the instance (A′, B′, C′, K) of the current problem is “yes” (exercise: why?). Note that this reduction runs in polynomial time because the elements of A, B, and C and the integer S are given in unary whereas A′, B′, C′, and K are in binary. Therefore, this is a polynomial-time reduction from N3DM to the current problem. This completes the proof that the current problem is NP-complete.

share|improve this answer
add comment

If you had just two sets, you'd have a well-known problem; you just order both sets, and match them up in reverse order, that is, largest in one set to smallest in the other, etc. With three sets, maybe it works to apply that solution iteratively, that is, match $A$ and $B$ in reverse order, then order the resulting set of products, then match it up with $C$ in reverse order.

Example: if $A=\{{1,6,8\}}$, $B=\{{3,5,7\}}$, $C=\{{2,4,9\}}$, then combine $A$ and $B$ to get $\{{(1)(7),(6)(5),(8)(3)\}}=\{{7,30,24\}}$, reorder as $\{{7,24,30\}}$, and match up with $C$ as $\{{(7)(9),(24)(4),(30)(2)\}}=\{{63,96,60\}}$, with sum 219.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.