Least-cost partition algorithms
type: Item
instance of: scholarly article
title: Least-cost partition algorithms
zbMATH Open document ID: 0679.90088
DOI: 10.1016/0166-218X(88)90097-2
author: Thomas J. jun. Marlowe
author: Marvin C. Paull
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
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.
reviewed by: Eugenia Duca
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 05A17
zbMATH DE Number: 4114421
zbMATH Keywords: least-cost partition problem
zbMATH Keywords: knapsack problem
zbMATH Keywords: average-case complexity
zbMATH Keywords: worst-cost complexity
MaRDI profile type: Publication
cites work: A program data flow analysis procedure
cites work: Q3241581
cites work: Q4079613
cites work: The Theory and Computation of Knapsack Functions
cites work: Q5675139
cites work: Q5772619
cites work: Q4162449
cites work: Q3885184
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Optimum binary search trees
cites work: Q4057549
cites work: Q5512461
cites work: Q4739657
cites work: Q4144192
cites work: Q4039733
cites work: Fast Algorithms for Solving Path Problems
cites work: Q3866122
Wikidata QID: Q126863030
full work available at URL: 0166-218x(88)90097-2
OpenAlex ID: W2083462149
Recommended article: Q4393369
Recommended article: Q3686722
Recommended article: Q4526868
Recommended article: Q4953911
Recommended article: Approximation Algorithms for the Minimum Convex Partition Problem
Recommended article: Partitioning a matrix to minimize the maximum cost
Recommended article: Q4816999
Recommended article: Minimum-cost load-balancing partitions
Recommended article: Approximation algorithms for array partitioning problems
description: scientific article; zbMATH DE number 4114421