2015/07/08 by Konstantinos Koiliaris, Chao Xu, Koiliaris, Konstantinos +1 · 3 voices · 1 citation
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Image Retrieval and Classification Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.1507.02318
openalex publication_date 2015/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a multiset S of n positive integers and a target integer t, the subset sum problem is to decide if there is a subset of S that sums up to t. We present a new divide-and-conquer algorithm that computes all the realizable subset sums up to an integer u in \widetildeO (min\√(n)u,u4/3,σ\), where σ is the sum of all elements in S and \widetildeO hides polylogarithmic factors. This result improves upon the standard dynamic programming algorithm that runs in O(nu) time. To the best of our knowledge, the new algorithm is the fastest general algorithm for this problem. We also present a modified algorithm for cyclic groups, which computes all the realizable subset sums within the group in \widetildeO (min\√(n)m,m5/4\) time, where m is the order of the group.