Faster Pseudopolynomial Time Algorithms for Subset Sum
ACM Transactions on Algorithms · 31.07.2019 · 15 (3) · 1-20
DOI: 10.1145/3329863 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 12.06.2019. Verfasst von Konstantinos Koiliaris und 1 weiteren Autor:innen. Die Arbeit wurde bisher 38-mal zitiert (Crossref) und nennt 55 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Koiliaris, K., & Xu, C. (2019). Faster Pseudopolynomial Time Algorithms for Subset Sum. ACM Transactions on Algorithms, 15(3), 1-20. https://doi.org/10.1145/3329863
Vancouver
Koiliaris K, Xu C. Faster Pseudopolynomial Time Algorithms for Subset Sum. ACM Transactions on Algorithms. 2019;15(3):1-20. doi:10.1145/3329863
BibTeX
@article{Koiliaris2019,
author = {Koiliaris, Konstantinos and Xu, Chao},
title = {Faster Pseudopolynomial Time Algorithms for Subset Sum},
journal = {ACM Transactions on Algorithms},
year = {2019},
volume = {15},
number = {3},
pages = {1--20},
doi = {10.1145/3329863}
}
EUVIMED