EUVIMEDEUVIMED entdecken
Crossref

Faster Pseudopolynomial Time Algorithms for Subset Sum

Konstantinos Koiliaris, Chao Xu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →