Key points are not available for this paper at this time.
We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set X of n positive integers and a target t, Subset Sum asks whether some subset of X sums to t. Bringmann proposes an O (n + t) -time algorithm Bringmann SODA'17, and an open question has naturally arisen: can Subset Sum be solved in O (n + w) time? Here w is the maximum integer in X. We make a progress towards resolving the open question by proposing an O (n + wt) -time algorithm.
Chen et al. (Thu,) studied this question.