Online square-into-square packing
From MaRDI portal
Publication:521815
DOI10.1007/978-3-642-40328-6_10zbMATH Open1364.90288arXiv1403.5665OpenAlexW2159840642MaRDI QIDQ521815FDOQ521815
Sándor P. Fekete, Hella-Franziska Hoffmann
Publication date: 12 April 2017
Published in: Algorithmica, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Abstract: In 1967, Moon and Moser proved a tight bound on the critical density of squares in squares: any set of squares with a total area of at most 1/2 can be packed into a unit square, which is tight. The proof requires full knowledge of the set, as the algorithmic solution consists in sorting the objects by decreasing size, and packing them greedily into shelves. Since then, the online version of the problem has remained open; the best upper bound is still 1/2, while the currently best lower bound is 1/3, due to Han et al. (2008). In this paper, we present a new lower bound of 11/32, based on a dynamic shelf allocation scheme, which may be interesting in itself. We also give results for the closely related problem in which the size of the square container is not fixed, but must be dynamically increased in order to ac- commodate online sequences of objects. For this variant, we establish an upper bound of 3/7 for the critical density, and a lower bound of 1/8. When aiming for accommodating an online sequence of squares, this corresponds to a 2.82...- competitive method for minimizing the required container size, and a lower bound of 1.33 . . . for the achievable factor.
Full work available at URL: https://arxiv.org/abs/1403.5665
Cites Work
- On strip packing With rotations
- A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
- Improved Approximation Algorithm for Two-Dimensional Bin Packing
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- Packing d-Dimensional Bins in d Stages
- Rectangle packing with one-dimensional resource augmentation
- A harmonic algorithm for the 3D strip packing problem
- A Polynomial Time Approximation Scheme for the Square Packing Problem
- A \((5/3+\varepsilon)\)-approximation for strip packing
- TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING
- Maximizing the total profit of rectangles packed into a rectangle
- A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
- On packing of squares and cubes
- New Approximability Results for Two-Dimensional Bin Packing
- Resource augmentation in two-dimensional packing with orthogonal rotations
- Packing into the smallest square: worst-case analysis of lower bounds
- Approximation algorithms for orthogonal packing problems for hypercubes
- On Two Dimensional Packing
- Mathematical Foundations of Computer Science 2005
- Online removable square packing
- New Approximability Results for 2-Dimensional Packing Problems
- Title not available (Why is that?)
- Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
- On-line packing sequences of cubes in the unit cube
- Online square and cube packing
- Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing
- Some packing and covering theorems
- Online Square Packing
- Online square packing with gravity
- Bounds for online bounded space hypercube packing
- On packing rectangles with resource augmentation: maximizing the profit
- Title not available (Why is that?)
- Online square-into-square packing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Packing Squares in Rectangles I
- On packing squares into a rectangle
Cited In (9)
- On-line potato-sack algorithm efficient for packing into small boxes
- Split packing: algorithms for packing circles with optimal worst-case density
- Online packing of \(d\)-dimensional boxes into the unit cube
- Online Square Packing
- On-line Packing Cubes into $n$ Unit Cubes
- Improved Bound for Online Square-into-Square Packing
- Approximation and Online Algorithms
- Online square-into-square packing
- Online circle and sphere packing
This page was built for publication: Online square-into-square packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521815)
