Saving space by algebraization

2010/06/05 by Daniel Lokshtanov, Jesper Nederlof · 2 citations
Computer Science · Mathematics · #Constraint Satisfaction and Optimization #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Knapsack problem #Time complexity #Polynomial #Mathematics #Polynomial-time approximation scheme #PSPACE #Space (punctuation) #Continuous knapsack problem #Matrix polynomial #Reciprocal polynomial #Discrete mathematics #Combinatorics #Computational complexity theory #Algebra over a field #Computer science #Algorithm #Pure mathematics #Mathematical analysis

paper · doi:10.1145/1806689.1806735

openalex publication_date 2010/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

The Subset Sum and Knapsack problems are fundamental NP-complete problems and the pseudo-polynomial time dynamic programming algorithms for them appear in every algorithms textbook. The algorithms require pseudo-polynomial time and space. Since we do not expect polynomial time algorithms for Subset Sum and Knapsack to exist, a very natural question is whether they can be solved in pseudo-polynomial time and polynomial space. In this paper we answer this question affirmatively, and give the first pseudo-polynomial time, polynomial space algorithms for these problems.

Citations

• The steiner problem in graphs
• Computing Partitions with Applications to the Knapsack Problem
• Set Partitioning via Inclusion-Exclusion
• Schnelle Multiplikation großer Zahlen

Cited by

• Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
• Steiner tree problem [wikipedia]

Related

• On the existence of polynomial-time algorithms to the subset sum problem
• Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
• Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
• An Improved Pseudopolynomial Time Algorithm for Subset Sum
• Fast Approximation Algorithms for Knapsack Problems