Online Sorting and Translational Packing of Convex Polygons
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Online Sorting and Translational Packing of Convex Polygons. / Aamand, Anders; Abrahamsen, Mikkel; Beretta, Lorenzo; Kleist, Linda.
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ed. / Nikhil Bansal; Viswanath Nagarajan. Society for Industrial and Applied Mathematics, 2023. p. 1806-1833.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Online Sorting and Translational Packing of Convex Polygons
AU - Aamand, Anders
AU - Abrahamsen, Mikkel
AU - Beretta, Lorenzo
AU - Kleist, Linda
PY - 2023
Y1 - 2023
N2 - We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used space. Among other variants, we consider strip packing and bin packing, where the container is the infinite horizontal strip [0, ∞) × [0,1] or a collection of 1 × 1 bins, respectively.If polygons may be rotated, there exist O(1)-competitive online algorithms for all problems at hand [Baker and Schwarz, SIAM J. Comput., 1983]. Likewise, if the polygons may not be rotated but only translated, then using a result from [Alt, de Berg and Knauer, JoCG, 2017] we can derive O(1)-approximation algorithms for all problems at hand. Thus, it is natural to conjecture that the online version of these problems, in which only translations are allowed, also admits a O(1)-competitive algorithm. We disprove this conjecture by showing a superconstant lower bound on the competitive ratio for several online packing problems.The offline approximation algorithm for translation-only packing sorts the convex polygons by their “natural slope”, so that they form a fan-like pattern. We prove that this step is essential, in the sense that packing polygons without rotating them is as hard as sorting numbers online. Technically, we prove lower bounds on the competitive ratio of translation-only online packing problems by reducing from a purpose-built novel and natural combinatorial problem that we call online sorting. In a nutshell, the problem requires us to place n numbers x1,…, xn coming online into an oversized array of length γn for γ ≥ 1, while minimizing the sum of absolute differences of consecutive numbers. Note that the offline optimum is achieved by sorting x1,…, xn. We show a superconstant lower bound on the competitive ratio of online sorting, for any constant γ. We prove that this yields superconstant lower bounds for all packing problems at hand. We believe that this technique is of independent interest since it uncovers a deep connection between inherently geometrical and purely combinatorial problems.As a complement, we also include algorithms for both online sorting and translation-only online strip packing with non-trivial competitive ratios. Our algorithm for strip packing relies on a new technique for recursively subdividing the strip into parallelograms of varying height, thickness and slope.
AB - We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used space. Among other variants, we consider strip packing and bin packing, where the container is the infinite horizontal strip [0, ∞) × [0,1] or a collection of 1 × 1 bins, respectively.If polygons may be rotated, there exist O(1)-competitive online algorithms for all problems at hand [Baker and Schwarz, SIAM J. Comput., 1983]. Likewise, if the polygons may not be rotated but only translated, then using a result from [Alt, de Berg and Knauer, JoCG, 2017] we can derive O(1)-approximation algorithms for all problems at hand. Thus, it is natural to conjecture that the online version of these problems, in which only translations are allowed, also admits a O(1)-competitive algorithm. We disprove this conjecture by showing a superconstant lower bound on the competitive ratio for several online packing problems.The offline approximation algorithm for translation-only packing sorts the convex polygons by their “natural slope”, so that they form a fan-like pattern. We prove that this step is essential, in the sense that packing polygons without rotating them is as hard as sorting numbers online. Technically, we prove lower bounds on the competitive ratio of translation-only online packing problems by reducing from a purpose-built novel and natural combinatorial problem that we call online sorting. In a nutshell, the problem requires us to place n numbers x1,…, xn coming online into an oversized array of length γn for γ ≥ 1, while minimizing the sum of absolute differences of consecutive numbers. Note that the offline optimum is achieved by sorting x1,…, xn. We show a superconstant lower bound on the competitive ratio of online sorting, for any constant γ. We prove that this yields superconstant lower bounds for all packing problems at hand. We believe that this technique is of independent interest since it uncovers a deep connection between inherently geometrical and purely combinatorial problems.As a complement, we also include algorithms for both online sorting and translation-only online strip packing with non-trivial competitive ratios. Our algorithm for strip packing relies on a new technique for recursively subdividing the strip into parallelograms of varying height, thickness and slope.
U2 - 10.1137/1.9781611977554.ch69
DO - 10.1137/1.9781611977554.ch69
M3 - Article in proceedings
SP - 1806
EP - 1833
BT - Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
A2 - Bansal, Nikhil
A2 - Nagarajan, Viswanath
PB - Society for Industrial and Applied Mathematics
Y2 - 22 January 2023 through 25 January 2023
ER -
ID: 382690205