Improved Pseudo-Polynomial-Time Approximation for Strip Packing

DOI10.4230/LIPIcs.FSTTCS.2016.9zbMath1393.68189arXiv1801.07541OpenAlexW2962917430MaRDI QIDQ4636556

Fabrizio Grandoni, Salvatore Ingala, Waldo Gálvez, Arindam Khan

Publication date: 19 April 2018

Full work available at URL: https://arxiv.org/abs/1801.07541

zbMATH Keywords

approximation algorithmsstrip packingrectangle packingcutting-stock problem

Mathematics Subject Classification ID

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

Related Items (8)

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

This page was built for publication: Improved Pseudo-Polynomial-Time Approximation for Strip Packing