Name
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. Our approach is based on algebraic methods and turns out to be useful for several other problems as well. Then we show how the framework yields polynomial space exact algorithms for the classical Traveling Salesman, Weighted Set Cover and Weighted Steiner Tree problems as well. Our algorithms match the time bound of the best known pseudo-polynomial space algorithms for these problems. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1806689.1806735 | STOC |
Keywords | Field | DocType |
subset sum,space efficient,framework yields polynomial space,fourier,dynamic programming,pseudo-polynomial space algorithm,knapsack problem,polynomial space algorithm,moebius,polynomial space,pseudo-polynomial time,algorithms textbook,polynomial time algorithm,weighted set cover,traveling salesman,polynomial time,dynamic programming algorithm,steiner tree problem,np complete problem,set cover | Discrete mathematics,Pseudo-polynomial time,Subset sum problem,Combinatorics,Steiner tree problem,Computer science,Continuous knapsack problem,PSPACE,Knapsack problem,Time complexity,NP | Conference |
ISSN | Citations | PageRank |
0737-8017 | 32 | 1.34 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Lokshtanov | 1 | 1438 | 110.05 |
| Jesper Nederlof | 2 | 294 | 24.22 |