Heuristic and exact algorithms for the precedence-constrained knapsack problem

DOI10.1023/A:1004649425222zbMath0997.90066OpenAlexW1499020692MaRDI QIDQ1586807

R. Smith

Publication date: 7 November 2002

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1004649425222

zbMATH Keywords

knapsack problemprecedence constraintsdynamic programming algorithmgreedy heuristicinverse precedence constrained knapsack problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (8)

Large-scale multi-period precedence constrained knapsack problem: A mining application ⋮ A pegging approach to the precedence-constrained knapsack problem ⋮ Piece selection algorithms for layered video streaming in P2P networks ⋮ Nonconvex piecewise linear knapsack problems ⋮ Sequential testing of \(n\)-out-of-\(n\) systems: precedence theorems and exact methods ⋮ Shift-and-merge technique for the DP solution of the time-constrained backpacker problem ⋮ Algorithms to solve the knapsack constrained maximum spanning tree problem ⋮ Exact and heuristic algorithms for dynamic tree simplification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• OPTIMAL TOOL MODULE DESIGN PROBLEM FOR NC MACHINE TOOLS
• The knapsack problem: A survey
• Computing Partitions with Applications to the Knapsack Problem
• A Depth-First Dynamic Programming Algorithm for the Tree Knapsack Problem
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees

This page was built for publication: Heuristic and exact algorithms for the precedence-constrained knapsack problem