.png){kind=icon}
.png){kind=icon}
Return
An Improved Pseudopolynomial Time Algorithm for Subset Sum
.png){kind=icon}
PRE
AI
DOI：10.1007/s10107-026-02348-y.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set X consisting of n positive integers and a target t, Subset Sum asks whether some subset of X sums to t. Bringmann proposed an O(n +t)-time algorithm [Bringmann SODA'17].An open question has naturally arisen: can Subset Sum be solved in O(n+ w)time? Here w is the largest integer in X. We make progress towards resolving the open question by proposing an O(n + root wt)-time algorithm.
Keywords:
Subset sum
Pseudo-polynomial time algorithms
Additive combinatorics