Parameterized complexity of strip packing and minimum volume packing

DOI10.1016/J.TCS.2016.11.034MaRDI QIDQ501656zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

strip packinggreedy packingvolume minimization

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(3)

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

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)