On approximating strip packing with a better ratio than 3/2

DOI10.1137/1.9781611974331.CH102zbMATH Open1394.68442OpenAlexW4231639237MaRDI QIDQ4575686FDOQ4575686

Giorgi Nadiradze, Andreas Wiese

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch102

Recommendations

• Approximate strip packing: revisited
• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• A new asymptotic approximation algorithm for 3-dimensional strip packing
• A Tight (3/2+ε) Approximation for Skewed Strip Packing.
• Improved pseudo-polynomial-time approximation for strip packing
• The problem of strip packing: An asymptotically exact approach
• Approximation algorithms for multiple strip packing
• A \((5/3 + \varepsilon )\)-approximation for strip packing
• A \((5/3+\varepsilon)\)-approximation for strip packing
• An approximation scheme for strip packing of rectangles with bounded dimensions

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (9)

• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• Complexity and inapproximability results for parallel task scheduling and strip packing
• A Tight (3/2+ε) Approximation for Skewed Strip Packing.
• Peak demand minimization via sliced strip packing
• Approximation and online algorithms for multidimensional bin packing: a survey
• An improved approximation algorithm for scheduling monotonic moldable tasks
• Approximate strip packing: revisited
• Improved approximation for two dimensional strip packing with polynomial bounded width
• Closing the Gap for Pseudo-Polynomial Strip Packing

This page was built for publication: On approximating strip packing with a better ratio than 3/2

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