Least-cost partition algorithms (Q1823166)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Least-cost partition algorithms |
scientific article |
Statements
Least-cost partition algorithms (English)
0 references
1989
0 references
The authors present three modifications of the standard \(O(n^ 2)\) dynamic programming algorithm for the knapsack problem. The first one restricts the number of possible substitutions, leading to significant average-case complexity improvement; worst-cost complexity remains \(O(n^ 2)\), but average-case complexity becomes \(O(n^{3/2})\). The second is a method of condensing partially developed solutions. The third is a prepass which eliminates some equations and guarantees O(n) or O(n log n) efficiency in a number of important special cases. Also, a related algorithm for the problem of partitioning an integer by integers not larger than some upper bound p, of complexity polynomial in p, is given.
0 references
least-cost partition problem
0 references
knapsack problem
0 references
average-case complexity
0 references
worst-cost complexity
0 references