Name
Abstract | ||
|---|---|---|
Fully polynomial approximation schemes for knapsack problems are presented. These algorithms are based on ideas of Ibarra and Kim, with modifications which yield better time and space bounds, and also tend to improve the practicality of the procedures. Among the principal improvements are the introduction of a more efficient method of scaling and the use of a median-finding routine to eliminate sorting. The 0-1 knapsack problem, for n items and accuracy ε > 0, is solved in n log1/ε + 1/ε4 time and On + 1/ε3 space. The time bound is reduced to On + 1/ε3 for the “unbounded” knapsack problem. For the “subset-sum” problem, On + 1/ε3 time and On + 1/ε2 space, or On + 1/ε2log1/ε time and space, are achieved. The “multiple choice” problem, with m equivalence classes, is solved in On log n + mn/ε time and On + m2/ε space. |
Year | DOI | Venue |
|---|---|---|
1977 | 10.1287/moor.4.4.339 | Math. Oper. Res. |
Keywords | Field | DocType |
space bound,polynomial approximation algorithm,principal improvement,knapsack problem,n item,m equivalence class,better time,multiple choice,efficient method,n log,electrical engineering,subset sum problem,rna,production,sorting,organizations,polynomials,algorithm design and analysis,computer science,optimization,cognition,indexing,data structures,accuracy,arithmetic,approximation algorithms,linear programming,artificial intelligence,indexes,upper bound | Approximation algorithm,Discrete mathematics,Data structure,Combinatorics,Polynomial,Upper and lower bounds,Continuous knapsack problem,Linear programming,Knapsack problem,Equivalence class,Mathematics | Conference |
Volume | Issue | Citations |
4 | 4 | 94 |
PageRank | References | Authors |
20.78 | 2 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| E. L. Lawler | 1 | 1102 | 585.42 |