In the subset sum problem, the input is a list of positive numbers summing up to $S$, and a target value $T<S$. The goal is to find a sub-list with the largest possible sum that is at most $T$.
This problem is NP-hard in general. However, if all numbers are small, e.g. at most $1$, then there is a simple additive approximation:
- Draw on the real line, starting at $0$, a segment of length $x$ for each input number $x$.
- Cut the line at $T$; this cuts at most one segment into two fractions.
- Remove the fraction from the subset. The sum of the remaining subset is at least $T-1$, which is an additive approximation of $1$.
If $T=S/2$, then a better approximation is possible:
- After cutting the line at $T$, check which half of the line contains the smaller fraction.
- Remove this fraction from the subset. The smaller fraction is at most $1/2$, so the sum of the remaining subset is at least $T-1/2$, which is an additive approximation of $1/2$.
QUESTION: Is it possible to attain an additive approximation of $1/2$ when $T$ is not exactly $S/2$, e.g. when $T=0.51 S$ or $T=0.49 S$?