An Improved Pseudopolynomial Time Algorithm for Subset Sum
<|reference_start|>An Improved Pseudopolynomial Time Algorithm for Subset Sum: 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 $\tilde{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 $\tilde{O}(n + \sqrt{wt})$-time algorithm.<|reference_end|>
@article{chen2024an,
    title={An Improved Pseudopolynomial Time Algorithm for Subset Sum},
    author={Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang},
    journal={arXiv preprint arXiv:2402.14493},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.14493},
    primaryClass={cs.DS}
}