Joint performance of greedy heuristics for the integer knapsack problem
type: Item
instance of: scholarly article
title: Joint performance of greedy heuristics for the integer knapsack problem
zbMATH Open document ID: 0831.90090
DOI: 10.1016/0166-218X(93)E0132-I
author: Rajeev Kohli
author: Ramesh Krishnamurti
published in: Discrete Applied Mathematics
publication date: 1995-02-01T00:00:00Z
review text: The authors consider an integer knapsack problem with values \(v(i)\), weights \(w(i)\) and capacity \(W\). Their goal is to analyse composite algorithms which compute the best heuristic solution obtained from subsequent applications of greedy algorithms with different selection rules. Four of these rules are considered which are based on sorting the items by (1) increasing weight, (2) decreasing value, (3) decreasing density \(v(i)/w(i)\), and (4) decreasing total value \([W/w(i)] v(i)\). The authors prove that in the worst case a composite of the density- ordered and total-value ordered greedy algorithm is superior to all other combinations of greedy heuristics.
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 716332
zbMATH Keywords: integer knapsack problem
zbMATH Keywords: worst case
zbMATH Keywords: greedy algorithm
reviewed by: Horst W. Hamacher
MaRDI profile type: Publication
cites work: Worst-Case Analysis of Heuristic Algorithms
cites work: Q4198056
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: A total-value greedy heuristic for the integer knapsack problem
cites work: Q4171868
cites work: New Algorithms for Bin Packing
full work available at URL: 0166-218x(93)e0132-i
OpenAlex ID: W2073388198
description: scientific article; zbMATH DE number 716332