Approximate Subset Sum with negative numbers

Question

I am interested in the approximation version of the Subset Sum problem with negative numbers. Wikipedia says there is an FPTAS algorithm for SS. That Wikipedia page states:

If all numbers are non-negative, the approximate subset sum is solvable in time polynomial in N and 1/c.

Similarly, in the CLRS version of the algorithm, the numbers are required to be positive. For the exact version there is this reduction that makes all numbers positive but I believe that it cannot be applied to the approximation version. Because the approximation algorithm behaves differently for larger numbers it would not give the same results if instead of -10 I have 10000. The trim function would cut a lot more numbers in the new, all positive version than in the original.

My question: Is there a FTPAS for General-SS, as defined below?

General-SS:
Given an input set $S=\{a_1,\dots,a_n\}$, where $a_i$ are possibly negative numbers, and a target $C$ find a subset $S'\subseteq S$ that sums to $C$.

All-positive-SS (defined below) has an FTPAS. Does this algorithm remains an FPTAS for General-SS?

All-positive-SS:
The same as General-SS, but where we restrict $a_i\geq 0$.

Alternatively, if we transform General-SS to All-positive-SS with the above reduction and then run the FPTAS algorithm for the new instance, does this also give an FTPAS for General-SS?

Answer 1

I believe the issue is with the definition of approximation.

Let's assume that we want to find a subset that sums to $C=0$. Then the approximate subset sum problem determines whether or not there is a subset within $(1-c)C$, which is just $0$.
Thus "approximate" subset sum is exactly subset sum if there are negative numbers (and thus can't be solved in polynomial time).

You can demand that the target value $C$ is nonzero, but this is insufficient---if $A$ is integral, then if $C = 1$ we can set $c = 1/2$ and again our algorithm is forced to obtain an exact answer. In fact, $C$ must be more than polynomial to avoid a contradiction. Thus, previous work has simply assumed a positive $A$, and we get a nice definition for what we want.

Note that if $A$ is positive, the interesting $C$ are very large, whereas with possibly-negative $A$ they may not be. This is part of the reason that positive $A$ is a sufficient condition for interesting approximation algorithms.

On the other hand, positive $A$ is probably not quite necessary. It is possible that one can limit $C$ and $A$ in such a way as to ensure that the problem is interesting even for possibly-negative $A$. Looking at the reduction, it seems that $C >> NM$ may do the trick (if $M$ is the absolute value of the smallest negative number in $A$); particularly if $C$ is exponential in $N$, and $M$ is polynomial (in other words, the negative numbers of $A$ are all very small). But at first glance, this seems to add complexity to the analysis without gaining much in return. Also, more work would have to be done to make sure this matches the approximate subset sum definition correctly.

---

As for the reduction: that reduction as-is does not work well if the goal is $C = 0$. Let's say, for example, that you start with a possibly-negative set $A = \{a_1,\ldots,a_N\}$, where the largest negative number is $\geq -M$, for a large positive $M$. We want to find a subset that sums to 0. Then, as per the reduction you cited, we construct $A' = \{a_1 + M,\ldots, a_N + M, M, \ldots, M\}$ with $N$ copies of $M$. We want to find a subset that sums to $NM$. This can trivially be accomplished by taking the $N$ copies of $M$.

Even if $C\neq 0$ this reduction doesn't work quite the way we would (probably) want. We obtain a solution within $[(1-c)(NM + C),NM+C]$. This may be significantly different than a solution within $[(1-c)C,C]$ for the original problem. However, as noted above, if $C >> NM$ this is somewhat close to a $(1-c)$ approximation ratio. We would need to be careful about solutions within $[C,NM+C]$, however.