A total-value greedy heuristic for the integer knapsack problem

DOI10.1016/0167-6377(92)90065-BMaRDI QIDQ1200766zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsdensity-ordered greedy heuristicgreedy heuristicinteger knapsackworst-case performance

Mathematics Subject Classification ID

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

Recommendations

• Average performance of greedy heuristics for the integer knapsack problem.
• Joint performance of greedy heuristics for the integer knapsack problem
• scientific article; zbMATH DE number 33203
• An extension of a greedy heuristic for the knapsack problem
• Greedy algorithm for the general multidimensional knapsack problem

Cites work

• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• scientific article; zbMATH DE number 3606249 (Why is no real title available?)
• When the Greedy Solution Solves a Class of Knapsack Problems
• Worst-Case Analysis of Heuristic Algorithms

Cited in

(14)

• An extension of a greedy heuristic for the knapsack problem
• A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem
• A complementary greedy heuristic for the knapsack problem
• Joint performance of greedy heuristics for the integer knapsack problem
• Average performance of greedy heuristics for the integer knapsack problem.
• A bi-level model and memetic algorithm for arc interdiction location-routing problem
• A heuristic algorithm for a chance constrained stochastic program
• Algorithms with guarantee value for knapsack problems
• Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
• On the optimality of the greedy solutions of the general knapsack problems
• On the proximity of the optimal values of the multi-dimensional knapsack problem with and without the cardinality constraint
• Integer knapsack problems with profit functions of the same value range
• LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup
• Sparse approximation in lattices and semigroups

This page was built for publication: A total-value greedy heuristic for the integer knapsack problem

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