Improved approximation for two dimensional strip packing with polynomial bounded width

DOI10.1016/j.tcs.2019.04.002zbMath1430.68449arXiv1610.04430OpenAlexW2944624729WikidataQ127904035 ScholiaQ127904035MaRDI QIDQ2272375

Malin Rau, Klaus Jansen

Publication date: 10 September 2019

Published in: Theoretical Computer Science, WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmstrip packingstructure analysispseudo-polynomialstructural lemmapseudo-polynomial running time

Mathematics Subject Classification ID

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

Related Items (8)

Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A reinforcement learning iterated local search for makespan minimization in additive manufacturing machine scheduling problems ⋮ A tight \((3/2+\varepsilon)\)-approximation for skewed 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

Cites Work

• A \((5/3+\varepsilon)\)-approximation for strip packing
• Rectangle packing with one-dimensional resource augmentation
• A 2.5 times optimal algorithm for packing in two dimensions
• Improved approximation for two dimensional strip packing with polynomial bounded width
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
• A algorithm for two-dimensional packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• On approximating strip packing with a better ratio than 3/2
• Improved Pseudo-Polynomial-Time Approximation for Strip Packing
• Approximation Algorithms for Scheduling Parallel Jobs
• Complexity and inapproximability results for parallel task scheduling and strip packing

This page was built for publication: Improved approximation for two dimensional strip packing with polynomial bounded width