Faster space-efficient algorithms for subset sum and k-sum

DOI10.1145/3055399.3055467MaRDI QIDQ4977972zbMATH OpenOpenAlexFDO

Authors N. Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3055399.3055467

zbMATH Keywords

randomized algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Combinatorial optimization (90C27)

Recommendations

• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Space-efficient randomized algorithms for \(k\)-sum
• A near-linear pseudopolynomial time algorithm for subset sum
• Faster algorithms for \(k\)-subset sum and variations
• Space-time tradeoffs for subset sum: an improved worst case algorithm

Cited in

(15)

• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• scientific article; zbMATH DE number 7378707 (Why is no real title available?)
• A near-linear pseudopolynomial time algorithm for subset sum
• Space-efficient randomized algorithms for \(k\)-sum
• Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Fast modular subset sum using linear sketching
• Space-efficient approximations for subset sum
• Space-time tradeoffs for subset sum: an improved worst case algorithm
• Improved combinatorial algorithms for the inhomogeneous short integer solution problem
• scientific article; zbMATH DE number 7525510 (Why is no real title available?)
• Saving space by algebraization
• Faster algorithms for \(k\)-subset sum and variations
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems

This page was built for publication: Faster space-efficient algorithms for subset sum and \(k\)-sum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977972)