# Possible reduction from SUBSET-SUM

Given is a multiset $$S$$, a finite set $$T = \{t_1, t_2, t_3\}$$, and an integer $$k \in \mathbb{N}$$.

Let $$v(t_j)$$ be a set of values $$\in \mathbb{R^+}$$ of length $$|T|$$ that can be assigned to $$s_i$$, and $$c(t_j)$$ be the cost of assigning $$v(t_j)$$ to $$s_i$$. Since $$S$$ is a multiset, assigning $$v(t_j)$$ to $$s_i$$ will affect every occurrance of $$s_i$$.

Given that $$v(t_j)$$ and $$c(t_j)$$ are known, which assignment of $$v(t_j)$$ to $$s_i$$ gives a value ($$\sum_{s_i \in S}$$) either equal to or as close as possible to $$k$$ that has the least cost?

Start of example

$$S=\{s_0, s_1, s_2, s_3, s_4, s_5, s_4, s_3, s_2, s_1\}$$, $$k = 100$$,

$$v(t_j) = \{5, 12.5, 50\}$$, and $$c(t_j)=\{10, 100, 1000\}$$.

We observe that the multiplicity of $$s_1,s_2,s_3,s_4$$ is $$2$$. Thus, assigning $$t_2$$ to those elements in the set gives $$12.5 * 2 * 4 = 100$$, and a cost of $$c(t_2) * 4 = 400$$.

End of example

Now, I am suspecting the SUBSET-SUM problem can be reduced to this problem. As far as I know, however, SUBSET-SUM specifies that the values either sum up to exactly $$k$$, OR is at most $$k$$, being as close as possible.

Assume $$k = 100$$, but the values of $$v(t_j)$$ are different. Then, assume two solutions that are just as close to $$k$$, but the first being less than $$k$$ and the last being greater than $$k$$, e.g., $$98$$ and $$102$$. Also, the cost of the first solution larger than the last.

Of course, the cheapest solution is the preferred one, but the value is greater than $$k$$; can the solution yielding $$102$$ be considered a solution at all?

When it comes to attempting to reduce SUBSET-SUM to this problem, I am not sure where to start, but I can definetly see the relation between them. I am looking for guidelines on how to go about the reduction, if it actually is possible.

• Do you always have $|T|=3$?
– D.W.
Mar 23 at 4:47
• What do you mean by an assignment? Do you have a requirement that no two $t_j$'s be assigned to the same $s_i$? Can one $t_j$ be assigned to two different $s_i$'s?
– D.W.
Mar 23 at 4:48
• @D.W. In my case, yes. However, if it possible to generalize it later for all sizes of T, that would be an interesting modification. Mar 23 at 10:09
• @D.W. By assignment, I mean that initially, $s_i$ does not have a value, however, the multiplicity of $s_i$ is known. Indeed, no two $t_j$'s can be assigned to the same $s_i$, but every $t_j$ can be assigned to every $s_i$. For instance, I can assign either nothing, or $t_1$, or $t_2$, or $t_3$ to $s_i$. After the assignment, every occurance of $s_i$ is affected, e.g., every occurance of $s_2$ if $s_2$ is assigned a value. The cost however, remains the same. Mar 23 at 10:27

After some research, this problem seems more related to KNAPSACK rather than SUBSET-SUM. From Garey & Johnson (1979)[p.247], KNAPSACK is defined as:

Instance: Finite set $$U$$, for each $$u \in U$$, a size $$s(u) \in \mathbb{Z^+}$$ and a value $$v(u) \in \mathbb{Z^+}$$, and positive integers $$B$$ and $$K$$.

Question: Is there a subset $$U' \subseteq U$$ such that $$\sum_{u \in U'}s(u) \leq B$$ and such that $$\sum_{u \in U'}v(u) \geq K$$?

Comments: If $$v(u) = s(u)$$ for all $$u \in U$$, then the problem is SUBSET-SUM.

The problem in question can be re-formulated as:

Finite sets $$S$$ and $$T = \{t_0, t_1, t_2, t_3\}$$, for each $$t \in T$$, a cost $$c(t) \in \mathbb{Z^+}$$ and a value $$v(t) \in \mathbb{Z^+}$$, and a positive integer $$K$$. Let $$v(t)$$ be a value that can be assigned to any $$S \in S$$, and $$c(t)$$ be the cost of assigning $$v(t)$$. $$|T| = |v(t)| = |c(t)| = 4$$ for all instances of the problem.

Let $$Q = \{s_1t_0, s_1t_2, s_1t_2, s_1t_3, \dots, s_it_3\}$$ be the set containing every possible assignment, such that $$|Q| = |T|^{|S|} = 4^{|S|}$$ Then, let $$c(q)$$ be the cost of assigning $$t$$ to $$s$$, and $$v(q)$$ be the value of the assignment.

Instance: Finite set $$Q$$, for each $$q \in Q$$, a cost $$c(q) \in \mathbb{R^+}$$ and a value $$v(q) \in \mathbb{R^+}$$, and a positive integer $$K$$.

Question: Is there a subset $$Q' \subseteq Q$$ such that $$\sum_{q \in Q'} \geq K$$?

Final remarks: We can observe that by constructing the set $$Q$$, the problem formulation is nearly identical with Garey & Johnson's formulation of KNAPSACK. The only notable difference I can see is that the problem in question does not have a capacity $$B$$. This "constraint" can be added for a reduction, but is somewhat trivial. Also note that $$S$$ is now denoted as a set, not a multiset, e.g., a set of all the unique elements in the set $$S$$ from the original question.