An approximation scheme for strip packing of rectangles with bounded dimensions

DOI10.1016/S0166-218X(97)00130-3MaRDI QIDQ1383370zbMATH OpenFDO

Authors W. Fernandez de la Vega, V. Zissimopoulos

Publication date 12 August 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

strip-packing problem

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99) Combinatorial aspects of packing and covering (05B40)

Recommendations

• A \((5/3 + \varepsilon )\)-approximation for strip packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A \((5/3+\varepsilon)\)-approximation for strip packing
• New Approximability Results for 2-Dimensional Packing Problems

Cites work

• A algorithm for two-dimensional packing
• Bin packing can be solved within 1+epsilon in linear time
• Integer Programming with a Fixed Number of Variables
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• The NP-completeness column: An ongoing guide
• Time bounds for selection

Cited in

(19)

• An approximation scheme for scheduling independent jobs into subcubes of a hypercube of fixed dimension
• Approximate strip packing: revisited
• An L-approach for packing (ℓ, w)-rectangles into rectangular and L-shaped pieces
• A \((5/3 + \varepsilon )\)-approximation for strip packing
• The two-dimensional cutting stock problem revisited
• Models of the nonguillotine sheet and strip rectangular packing problem
• On approximating strip packing with a better ratio than 3/2
• An approximation algorithm for sequential rectangle placement
• Strip packing with precedence constraints and strip packing with release times
• A near-optimal solution to a two-dimensional cutting stock problem
• An exact method for the 2D guillotine strip packing problem
• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• Two-dimensional packing problems: a survey
• High multiplicity strip packing with three rectangle types
• scientific article; zbMATH DE number 3942360 (Why is no real title available?)
• Parameterized complexity of strip packing and minimum volume packing
• scientific article; zbMATH DE number 3904609 (Why is no real title available?)
• A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks
• A \((5/3+\varepsilon)\)-approximation for strip packing

This page was built for publication: An approximation scheme for strip packing of rectangles with bounded dimensions

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