A note on the Kenyon-Remila strip-packing algorithm

DOI10.1016/J.IPL.2011.10.003zbMATH Open1233.68141OpenAlexW2071605324MaRDI QIDQ763478FDOQ763478

Authors: Maxim Sviridenko 

Publication date: 9 March 2012

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

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

Recommendations

• Approximate strip packing: revisited
• A \((5/3 + \varepsilon )\)-approximation for strip packing
• A \((5/3+\varepsilon)\)-approximation for strip packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• New Approximability Results for 2-Dimensional Packing Problems

zbMATH Keywords

approximation algorithmsstrip packingbin packing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• A near-optimal solution to a two-dimensional cutting stock problem
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• New Approximability Results for 2-Dimensional Packing Problems

Cited In (3)

• An improved approximation algorithm for scheduling monotonic moldable tasks
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• Closing the Gap for Pseudo-Polynomial Strip Packing

This page was built for publication: A note on the Kenyon-Remila strip-packing algorithm

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