Possible reduction from SUBSET-SUM

Question

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.

Answer 1

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.