Average performance of greedy heuristics for the integer knapsack problem.

DOI10.1016/S0377-2217(02)00810-XzbMath1099.90053MaRDI QIDQ1420409

Prakash Mirchandani, Ramesh Krishnamurti, Rajeev Kohli

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

Integer programming; Heuristics; Combinatorial optimization; Knapsack; Probabilistic algorithm

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

90B80: Discrete location and assignment

Related Items

Tight bounds for periodicity theorems on the unbounded knapsack problem, Using modifications to Grover's search algorithm for quantum global optimization

Uses Software

• Knapsack

Cites Work

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