Linear time-approximation algorithms for bin packing

DOI10.1016/S0167-6377(99)00077-2zbMath0960.90096MaRDI QIDQ1591548

R. Smith

Publication date: 20 May 2001

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

zbMATH Keywords

linear time algorithmbin packingabsolute worst-case ratio

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (7)

Bin packing with divisible item sizes and rejection penalties ⋮ Bin packing with rejection revisited ⋮ A 4-space bounded approximation algorithm for online bin packing problem ⋮ Efficient algorithms for real-life instances of the variable size bin packing problem ⋮ A 3-approximation algorithm for two-dimensional bin packing ⋮ NF-Based Algorithms for Online Bin Packing with Buffer and Item Size Limitation ⋮ NF-based algorithms for online bin packing with buffer and bounded item size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time bin-packing algorithm
• Bin packing can be solved within 1+epsilon in linear time
• A simple on-line bin-packing algorithm
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• On-line bin packing in linear time

This page was built for publication: Linear time-approximation algorithms for bin packing