Return to 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?

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?

I am intrested in the approximation version of the Subset Sum problem with negative numbers. We know that there is an FPTAS algorithm for SS wiki. In this wiki page it states

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

Again, 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.

If anyone know anything on that I would be grateful.

EDIT: I thought it is OK to just discuss a matter that concerns me and not provide a very specific question. But I will try to clarify:

I think the main question is this:

1) 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$.
Is there an FTPAS for this problem?

All-positive-SS:
If we restrict $a_i\geq 0$.
All-positive-SS has an FTPAS. Does this algorithm remains an FPTAS for General-SS?

2) Alternativelly, can we transform the General-SS to All-positive-SS with the above reduction, run the FPTAS algorithm for the new instance and claim tha this also gives an FTPAS for the General-SS?

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?

I am intrested in the approximation version of the Subset Sum problem with negative numbers. We know that there is an FPTAS algorithm for SS wiki. In this wiki page it states

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

Again, 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.

If anyone know anything on that I would be grateful.

I am intrested in the approximation version of the Subset Sum problem with negative numbers. We know that there is an FPTAS algorithm for SS wiki. In this wiki page it states

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

Again, 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.

If anyone know anything on that I would be grateful.

EDIT: I thought it is OK to just discuss a matter that concerns me and not provide a very specific question. But I will try to clarify:

I think the main question is this:

1) 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$.
Is there an FTPAS for this problem?

All-positive-SS:
If we restrict $a_i\geq 0$.
All-positive-SS has an FTPAS. Does this algorithm remains an FPTAS for General-SS?

2) Alternativelly, can we transform the General-SS to All-positive-SS with the above reduction, run the FPTAS algorithm for the new instance and claim tha this also gives an FTPAS for the General-SS?