On-line algorithms for packing rectangles into several strips

DOI10.1515/dma.2007.040zbMath1247.05055OpenAlexW1975014756MaRDI QIDQ5439071

S. N. Zhuk

Publication date: 8 February 2008

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma.2007.040

zbMATH Keywords

asymptotic multiplicative error

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of packing and covering (05B40)

Related Items

Application of Hadamard product to some combinatorial and probabilistic problems ⋮ On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis

Cites Work

• Shelf algorithms for on-line strip packing
• New algorithms for an ancient scheduling problem.
• An improved lower bound for on-line bin packing algorithms
• Multidimensional on-line bin-packing: An algorithm and its average-case analysis
• A better lower bound for on-line scheduling
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Grid scheduling by on-line rectangle packing
• Shelf Algorithms for Two-Dimensional Packing Problems
• Orthogonal Packings in Two Dimensions
• A algorithm for two-dimensional packing
• Better Bounds for Online Scheduling
• A Better Algorithm for an Ancient Scheduling Problem
• Approximate algorithms to pack rectangles into several strips