  We consider the SUBSET SUM problem and its important variants in this paper.
In the SUBSET SUM problem, a (multi-)set $X$ of $n$ positive numbers and a
target number $t$ are given, and the task is to find a subset of $X$ with the
maximal sum that does not exceed $t$. It is well known that this problem is
NP-hard and admits fully polynomial-time approximation schemes (FPTASs). In
recent years, it has been shown that there does not exist an FPTAS of running
time $\tilde\OO( 1/\epsilon^{2-\delta})$ for arbitrary small $\delta>0$
assuming ($\min$,+)-convolution conjecture~\cite{bringmann2021fine}. However,
the lower bound can be bypassed if we relax the constraint such that the task
is to find a subset of $X$ that can slightly exceed the threshold $t$ by
$\epsilon$ times, and the sum of numbers within the subset is at least
$1-\tilde\OO(\epsilon)$ times the optimal objective value that respects the
constraint. Approximation schemes that may violate the constraint are also
known as weak approximation schemes. For the SUBSET SUM problem, there is a
randomized weak approximation scheme running in time $\tilde\OO(n+
1/\epsilon^{5/3})$ [Mucha et al.'19]. For the special case where the target $t$
is half of the summation of all input numbers, weak approximation schemes are
equivalent to approximation schemes that do not violate the constraint, and the
best-known algorithm runs in $\tilde\OO(n+1/\epsilon^{{3}/{2}})$ time
[Bringmann and Nakos'21].
