1
$\begingroup$

Take a set $S = \{a_1, a_2, ..., a_n\}$ of integers $a_i$ and a set $G = \{b_1, b_2, ..., b_m\}$ of integers $b_j$.

If we ask the question, is there a subset $C \subseteq S$ such that the sum $(\sum_{a_i \in C} a_i) \in G$, and $m = 1$ this is the traditional subset sum problem. We add an additional restriction (so that this is a promise problem) that all $b_j \in G$ must be between the minimum sum and the maximum sum of subsets of $S$.

I have three questions regarding the case where $m \gt 1$.

1.) Is there a known name for this problem and has it been studied?

2.) Are there threshold results for this problem, or can threshold results from k-SAT problems be reduced to this problem?

3.) Are there known or obvious instances where this problem is trivial? Or in general does it remain NP-Complete?

Edit: Threshold results - for a uniformally random selected set $S$ and $G$ of given sizes whose integer members are limited in size (under the usual binary encoding) of $b$ bits, and for a fixed ratio $k = |G|/|S|$, is there a $k$ for which the multiple target subset sum problem becomes almost certainly satisfiable or unsatisfiable (in the manner of 3-SAT)?

$\endgroup$
  • 3
    $\begingroup$ For 3) It is still NPC: if $m$ is a parameter, then it is a generalization of SUBSET SUM. If $m$ is fixed, then given an instance of SUBSET SUM, simply multiply every $a_i$ and the target sum $B$ by $2^k$ s.t. $2^k > m(m+1)/2$ and set $m$ target integers $b_1=B, b_2 = a_1+1, b_3=a_1+2,...,b_m = a_1+{m-1}$. In both cases it also remains solvable in pseudo-polynomial time. $\endgroup$ – Marzio De Biasi Dec 24 '14 at 8:20
  • $\begingroup$ @MarzioDeBiasi Nice reduction! $\endgroup$ – Jason Knight Dec 24 '14 at 16:16
  • $\begingroup$ What does "threshold results" mean in this context? Please clarify by editing the question. $\endgroup$ – Tsuyoshi Ito Dec 25 '14 at 14:42
  • $\begingroup$ I cannot understand your edit about "threshold results." Which set are S and G chosen from? In addition, intuitively, increasing |S| makes the instance more likely to be satisfiable, and so does increasing |G|, so fixing the ratio |G|/|S| does not seem to make sense. $\endgroup$ – Tsuyoshi Ito Dec 30 '14 at 7:27
  • $\begingroup$ @Tsuyoshilto These sets are chosen uniformally from all sets of a certain size whose integer members are within a certain bit size limit $b$ (under the usual binary encoding). I would certainly welcome a characterization of threshold that doesn't take a ratio if it captured the asymptotic likelihood of a given instance (taken uniformally) to be varifiable. Thanks for the questions! $\endgroup$ – Jason Knight Dec 30 '14 at 17:33
3
$\begingroup$

For what regards point 3: the problem remains NP-complete:

  • if $m$ is a parameter, then it is simply a generalization of SUBSET SUM;

  • if $m$ is fixed, then given an instance of SUBSET SUM, simply multiply every $a_i$ and the target sum $B$ by $p = 2^k$ s.t. $2^k>m(m+1)/2$ and set $m$ target integers in this way:

$G = \{ b_1=B,b_2=a_1+1,b_3=a_1+2,...,b_m=a_1+(m−1)\}$.

In both cases the problem remains solvable in pseudo-polynomial time.

For what regards point 2) you can find some information related to the density analysis for the ("simpler") SUBSET-SUM problem (it is usually defined in terms of $n/m$ where $n$ is the number of elements of the input set and $m$ is its maximum); e.g.: O'Neil, Thomas E. "On Clustering in the Subset Sum Problem." Proceedings of the 44th Midwest Instruction and Computing Symposium (Duluth, MN, 2011).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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