A linear time bin-packing algorithm

DOI10.1016/0167-6377(85)90028-8MaRDI QIDQ1062626zbMATH OpenOpenAlexFDO

Authors Chip Martel

Publication date 1985

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(85)90028-8

zbMATH Keywords

cutting stocklinear time bin-packing algorithmoff-line bin-packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Review text

In the bin-packing problem a list L of numbers in (0,1] is to be packed into unit capacity bins. Let \(L^*\) denote the minimum number of bins required. We present a linear time bin-packing algorithm for the off-line version of this problem. The algorithm uses at most \((4/3)L^*+2\) bins.

Recommendations

• Linear time-approximation algorithms for bin packing
• Improved Space for Bounded-Space, On-Line Bin-Packing
• A 5/4 linear time bin packing algorithm
• Variable Sized Bin Packing
• On-line bin packing in linear time

Cites work

• A class of simple stochastic online bin packing algorithms
• Bin packing can be solved within 1+epsilon in linear time
• Fast algorithms for bin packing
• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• New Algorithms for Bin Packing
• Time bounds for selection

Cited in

(4)

• A linear approximation algorithm for bin packing with absolute approximation factor \(\frac {3}{2}\)
• Linear time-approximation algorithms for bin packing
• A 5/4 linear time bin packing algorithm
• A note on the minimum bounded edge-partition of a tree

This page was built for publication: A linear time bin-packing algorithm

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