Least-cost partition algorithms (Q1823166): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A program data flow analysis procedure / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3241581 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4079613 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Theory and Computation of Knapsack Functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5675139 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5772619 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4162449 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3885184 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimum binary search trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4057549 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Least-cost partition algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5512461 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4739657 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4144192 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4039733 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Algorithms for Solving Path Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3866122 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126863030 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0166-218x(88)90097-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2083462149 / rank | |||
Normal rank |
Latest revision as of 12:15, 30 July 2024
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