文章基本信息

标题：A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum
本地全文：下载
作者：Ce Jin ; Hongxun Wu
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2018
卷号：69
页码：1-6
DOI：10.4230/OASIcs.SOSA.2019.17
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given a multiset S of n positive integers and a target integer t, the Subset Sum problem asks to determine whether there exists a subset of S that sums up to t. The current best deterministic algorithm, by Koiliaris and Xu [SODA'17], runs in O~(sqrt{n}t) time, where O~ hides poly-logarithm factors. Bringmann [SODA'17] later gave a randomized O~(n + t) time algorithm using two-stage color-coding. The O~(n+t) running time is believed to be near-optimal. In this paper, we present a simple and elegant randomized algorithm for Subset Sum in O~(n + t) time. Our new algorithm actually solves its counting version modulo prime p>t, by manipulating generating functions using FFT.
关键词：subset sum; formal power series; FFT