Space-efficient approximations for subset sum

DOI10.1145/2894843MaRDI QIDQ4973861zbMATH OpenOpenAlexWikidataFDO

Authors Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Publication date 6 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

FPTASfully polynomial-time approximation schemesknapsack problemmonotone circuitsone-pass streaming algorithm

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Recommendations

• The complexity of unary subset sum
• scientific article; zbMATH DE number 1104339
• A Fast Approximation Algorithm For The Subset-Sum Problem
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Faster space-efficient algorithms for subset sum and k-sum

Cited in

(6)

• A low-space algorithm for the subset-sum problem on GPU
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• The complexity of unary subset sum
• Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• On binary solutions to systems of equations

This page was built for publication: Space-efficient approximations for subset sum

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