The complexity of unary subset sum

DOI10.1007/978-3-642-32241-9_39MaRDI QIDQ2914349zbMATH OpenOpenAlexFDO

Authors Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Publication date 25 September 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32241-9_39

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Space-efficient approximations for subset sum
• A near-linear pseudopolynomial time algorithm for subset sum
• Subset sum in the absence of concentration
• Subset-sum problems with different summands: Computation
• Faster Pseudopolynomial Time Algorithms for Subset Sum

Cited in

(1)

• Space-efficient approximations for subset sum

This page was built for publication: The complexity of unary subset sum

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