A 3-approximation algorithm for two-dimensional bin packing

DOI10.1016/j.orl.2004.04.004zbMath1099.90055OpenAlexW2081615832MaRDI QIDQ2488211

Guo-Chuan Zhang

Publication date: 25 August 2005

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

Full work available at URL: https://doi.org/10.1016/j.orl.2004.04.004

zbMATH Keywords

Approximation algorithmsBin packingAbsolute worst-case ratio

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Randomized algorithms (68W20)

Related Items (6)

Two for One: Tight Approximation of 2D Bin Packing ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Packing Rectangles into 2OPT Bins Using Rotations ⋮ Absolute approximation ratios for packing rectangles into bins ⋮ TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING ⋮ New approximability results for two-dimensional bin packing

Cites Work

• Recent advances on two-dimensional bin packing problems
• Bin packing can be solved within 1+epsilon in linear time
• Linear time-approximation algorithms for bin packing
• Two-dimensional packing problems: a survey
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Orthogonal Packings in Two Dimensions
• On Packing Two-Dimensional Bins
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A 3-approximation algorithm for two-dimensional bin packing