1
$\begingroup$

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?

  • 0
    For equation editing, you could see http://meta.math.stackexchange.com/questions/1773/do-we-have-an-equation-editing-howto to get started.2012-06-03

2 Answers 2

0

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.

0

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.