A total-value greedy heuristic for the integer knapsack problem

DOI10.1016/0167-6377(92)90065-BzbMath0757.90061OpenAlexW1972327555MaRDI QIDQ1200766

Rajeev Kohli, Ramesh Krishnamurti

Publication date: 16 January 1993

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90065-b

zbMATH Keywords

worst-case performanceapproximation algorithmsinteger knapsackgreedy heuristicdensity-ordered greedy heuristic

Mathematics Subject Classification ID

Integer programming (90C10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Joint performance of greedy heuristics for the integer knapsack problem ⋮ LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup ⋮ A heuristic algorithm for a chance constrained stochastic program ⋮ Average performance of greedy heuristics for the integer knapsack problem. ⋮ A bi-level model and memetic algorithm for arc interdiction location-routing problem ⋮ On the Proximity of the Optimal Values of the Multi-dimensional Knapsack Problem with and Without the Cardinality Constraint

Cites Work

• Worst-Case Analysis of Heuristic Algorithms
• When the Greedy Solution Solves a Class of Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Unnamed Item