Faster Pseudopolynomial Time Algorithms for Subset Sum
Authors:
Top Cited Papers
Open Access
- 12 June 2019
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 15 (3) , 1-20
Abstract
Given a (multi) set S of n positive integers and a target integer u , the subset sum problem is to decide if there is a subset of S that sums up to u . We present a series of new algorithms that compute and return all the realizable subset sums up to the integer u in Õ(min { √ n u , u 5/4 ,σ }), where σ is the sum of all elements of S and Õ hides polylogarithmic factors. We also present a modified algorithm for integers modulo m , which computes all the realizable subset sums modulo m in Õ(min { √ n m , m 5/4 }) time. Our contributions improve upon the standard dynamic programming algorithm that runs in O ( nu ) time. To the best of our knowledge, the new algorithms are the fastest deterministic algorithms for this problem. The new results can be employed in various algorithmic problems, from graph bipartition to computational social choice. Finally, we also improve a result on covering Z m , which might be of independent interest.Keywords
This publication has 33 references indexed in Scilit:
- On covering by translates of a setRandom Structures & Algorithms, 2010
- On complete subsets of the cyclic groupJournal of Combinatorial Theory, Series A, 2008
- Parallel machine scheduling with job assignment restrictionsNaval Research Logistics (NRL), 2006
- Dynamic Programming on the Word RAMAlgorithmica, 2003
- Dynamic Programming Revisited: Improving Knapsack AlgorithmsComputing, 1999
- Linear Time Algorithms for Knapsack Problems with Bounded WeightsJournal of Algorithms, 1999
- Minimum Range Balanced Cuts via Dynamic Subset SumsJournal of Algorithms, 1997
- Subset sumsJournal of Number Theory, 1987
- Computing Partitions with Applications to the Knapsack ProblemJournal of the ACM, 1974
- Notes on the theory of dynamic programming IV ‐ Maximization over discrete setsNaval Research Logistics Quarterly, 1956