Modified subset sum heuristics for bin packing

DOI10.1016/j.ipl.2005.04.005zbMath1184.68661WikidataQ61638363 ScholiaQ61638363MaRDI QIDQ1044695

Alberto Caprara, Ulrich Pferschy

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.04.005

zbMATH Keywords

analysis of algorithms; worst-case analysis; bin packing; subset sum heuristic

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

Related Items

Parametric packing of selfish items and the subset sum algorithm, Constrained order packing: comparison of heuristic approaches for a new bin packing problem, A hybrid algorithm for constrained order packing, Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem, Heuristics for the variable sized bin-packing problem, Minimizing the number of stations and station activation costs for a production line, Efficient algorithms for real-life instances of the variable size bin packing problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Worst-case analysis of the subset sum algorithm for bin packing.
• Approximation algorithms for knapsack problems with cardinality constraints
• Dynamic programming revisited: Improving knapsack algorithms
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• Analysis of a Compound Bin Packing Algorithm
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• New heuristics for one-dimensional bin-packing