Least-cost partition algorithms

Combinatorial aspects of partitions of integers (05A17) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Dynamic programming (90C39)

Review text

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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Least-cost partition algorithms

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