Parameterized complexity of strip packing and minimum volume packing

DOI10.1016/J.TCS.2016.11.034zbMATH Open1356.68091OpenAlexW2560694610MaRDI QIDQ501656FDOQ501656

Authors: Pradeesha Ashok, Sudeshna Kolay, Saket Saurabh, S. M. Meesum 

Publication date: 9 January 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.11.034

Recommendations

• Two- and three-dimensional parametric packing
• An approximation scheme for strip packing of rectangles with bounded dimensions
• New Approximability Results for 2-Dimensional Packing Problems
• A \((5/3 + \varepsilon )\)-approximation for strip packing

zbMATH Keywords

strip packinggreedy packingvolume minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Cites Work

• Parametrized complexity theory.
• A near-optimal solution to a two-dimensional cutting stock problem
• Polynomiality for bin packing with a constant number of item types
• Parameterized algorithms
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• Title not available (Why is that?)
• Two-dimensional packing problems: a survey
• A note on online strip packing
• Improved lower bound for online strip packing
• Bin packing with fixed number of bins revisited
• Online strip packing with modifiable boxes
• Approximating minimum-area rectangular and convex containers for packing convex polygons
• Title not available (Why is that?)
• Optimal rectangle packing: an absolute placement approach
• Title not available (Why is that?)

Cited In (3)

• (Re)packing equal disks into rectangle
• Complexity results for the horizontal bar packing problem
• Grid recognition: classical and parameterized computational perspectives

This page was built for publication: Parameterized complexity of strip packing and minimum volume packing

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