Average performance of greedy heuristics for the integer knapsack problem.

DOI10.1016/S0377-2217(02)00810-XMaRDI QIDQ1420409zbMATH OpenOpenAlexFDO

Authors Rajeev Kohli, Ramesh Krishnamurti, P. Mirchandani

Publication date 2 February 2004

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0377-2217(02)00810-x

zbMATH Keywords

Combinatorial optimizationHeuristicsInteger programmingKnapsackProbabilistic algorithm

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A total-value greedy heuristic for the integer knapsack problem
• Joint performance of greedy heuristics for the integer knapsack problem
• Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.
• An extension of a greedy heuristic for the knapsack problem
• A class of generalized greedy algorithms for the multi-knapsack problem

Cites work

• A probabilistic analysis of multiprocessor list scheduling: the erlang case
• A probabilistic analysis of the next fit decreasing bin packing heuristic
• A stochastic model of bin-packing
• A total-value greedy heuristic for the integer knapsack problem
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Asymptotic Properties of the Quadratic Assignment Problem
• Average Performance of Heuristics for Satisfiability
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 1302173 (Why is no real title available?)
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Probabilistic Analysis of the Planar k-Median Problem
• Probabilistic bounds for dual bin-packing
• The average-case analysis of some on-line algorithms for bin packing
• The Minimum Satisfiability Problem
• Travelling Salesman and Assignment Problems: A Survey
• Unbounded knapsack problem: Dynamic programming revisited
• Worst-Case Analysis of Heuristic Algorithms

Cited in

(8)

• A total-value greedy heuristic for the integer knapsack problem
• Joint performance of greedy heuristics for the integer knapsack problem
• Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.
• Average-case performance of rollout algorithms for knapsack problems
• Tight bounds for periodicity theorems on the unbounded knapsack problem
• scientific article; zbMATH DE number 1264402 (Why is no real title available?)
• Greedy algorithms for the minimization knapsack problem: average behavior
• Using modifications to Grover's search algorithm for quantum global optimization

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Average performance of greedy heuristics for the integer knapsack problem.

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