6
$\begingroup$

In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$. The problem can be solved by dynamic programming in time $O(n T)$: for every $i\in\{1,\ldots,n\}$ and $j\in\{1,\ldots,T\}$, we compute whether it is possible to attain a sum of exactly $j$ using the inputs $x_1,\ldots,x_i$.

Suppose that, instead of finding a subset of sum exactly $T$, we only ask if there is a subset of sum between $T$ and $T+k n$, for some fixed integer $k$. Initially, I thought that this could be done faster: round down each input $x_i$ to the nearest multiple of $k$. The inaccuracy for each input is at most $k$, so the cumulative inaccuracy is at most $k n$. Now, we have to consider only $j\in\{1,\ldots,T\}$ which are multiples of $k$, so the run-time is in $O(n T / k)$. However, this solves a slightly different problem:

  • If there is a subset with sum $T$, then return a subset with sum in $(T- k n, T)$;
  • If there is no subset with sum between $T$ and $T+ n k$, then do not return a subset with sum $T$.

Is there an algorithm to decide whether there is a subset with sum in $\{T,\ldots, T+kn\}$, asymptotically faster than $O(n T)$, for example, in time $O(n T / k)$?

$\endgroup$
7
  • $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/51082/5038. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Feb 10, 2022 at 6:36
  • 1
    $\begingroup$ This is not a dynamic programming solution as the title suggests, but there is a near-linear $O((n + t) \mathrm{poly} \log (n + t))$ time randomized algorithm for the subset sum problem [1]. [1]: Karl Bringmann, A near-linear pseudopolynomial time algorithm for subset sum, SODA 2017 $\endgroup$
    – pcpthm
    Feb 10, 2022 at 13:15
  • $\begingroup$ @pcpthm interesting link, thanks! But it is still worse than $O(n T/k)$ when $k$ is large. $\endgroup$ Feb 10, 2022 at 13:23
  • 1
    $\begingroup$ @D.W. The policy in cstheory.SE is "Crossposting is permitted after a week has passed without a satisfying answer elsewhere". For this question, almost two months have passed, so I thought it was OK. I am sorry if I mis-interpreted the policy. $\endgroup$ Feb 12, 2022 at 16:40
  • $\begingroup$ Yes, that's part of the CS Theory.SE policy, but not the CS.SE policy. Cross-posting requires the OK of both communities. Please note that the CS Theory.SE policy also requires cross-linking both ways and updating both questions based on answers and comments received on the other site, which has not been followed here. $\endgroup$
    – D.W.
    Feb 13, 2022 at 0:15

1 Answer 1

-1
$\begingroup$

Dynamic programming solves the problem in $O(\sum v)$, where $\sum v$ is the sum of item sizes. The subset sum problem is trivial if the item sizes are small and only gets hard when the item sizes grow.

Finding an approximation without a precise range is roughly equivalent to solving the original problem with slightly smaller numbers. But solving it with an exact range is just as hard as the original problem if there is no solution.

Imagine I ask you to decide whether there exists a subset with sum $T \leq sum \leq T+d$. And in addition I guarantee there is no subset with $T < sum <T+d$. Then your problem is to decide whether there exists a subset with sum exactly $T$ or exactly $T+d$.

$\endgroup$
2
  • 2
    $\begingroup$ I am not sure I understand the last argument. Do you say that adding informatiom (guarantee) cannot make the problem harder? But with the additional information, maybe the original problem (decide whether there exists a subset with sum exactly $T$, assuming there are no subsets with $T < sum < T+d$) is easy? $\endgroup$ Dec 17, 2021 at 13:22
  • 1
    $\begingroup$ I don't understand how this answers the question. I don't understand what algorithm you have in mind for the problem. $\endgroup$
    – D.W.
    Feb 10, 2022 at 6:42

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.