0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Do you always have $|T|=3$? $\endgroup$
    – D.W.
    Mar 23, 2023 at 4:47
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Mar 23, 2023 at 4:48
  • $\begingroup$ @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. $\endgroup$ Mar 23, 2023 at 10:09
  • $\begingroup$ @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. $\endgroup$ Mar 23, 2023 at 10:27

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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