A note on the Kenyon-Remila strip-packing algorithm

DOI10.1016/J.IPL.2011.10.003MaRDI QIDQ763478zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(3)

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

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)