Worst-case analysis of the subset sum algorithm for bin packing.
type: Item
instance of: scholarly article
title: Worst-case analysis of the subset sum algorithm for bin packing.
zbMATH Open document ID: 1060.90061
DOI: 10.1016/S0167-6377(03)00092-0
author: Alberto Caprara
author: Ulrich Pferschy
published in: Operations Research Letters
publication date: 2004-01-05T00:00:00Z
review text: The authors investigate the asymptotic worst-case ratio of the subset sum heuristic for the bin packing problem (BPP). They prove a new lower bound on the optimal value of BPP and formulate a mathematical programming problem which they solve analytically. The optimal value of this program yields the upper bound \(\frac{4}{3}+\ln\left(\frac{4}{3}\right)\approx 1.6210\) on the worst-case ratio of the subset sum heuristic. It is also shown that for bounded item sizes the worst case ratio of the subset sum heuristic is inbetween that of the first fit and first fit decreasing heuristics.
reviewed by: Matthias Ehrgott
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 2021246
zbMATH Keywords: bin packing
zbMATH Keywords: subset sum heuristic
zbMATH Keywords: worst case analysis
Wikidata QID: Q61638372
describes a project that uses: Knapsack
MaRDI profile type: Publication
cites work: New heuristics for one-dimensional bin-packing
cites work: Fast algorithms for bin packing
cites work: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
cites work: Dynamic programming revisited: Improving knapsack algorithms
cites work: Linear Time Algorithms for Knapsack Problems with Bounded Weights
cites work: Q4245749
cites work: Computational study of a column generation algorithm for bin packing and cutting stock problems
DBLP publication ID: journals/orl/CapraraP04
description: scientific article; zbMATH DE number 2021246