Algorithms for Geometric Packing and Covering Problems

Abstract

We study two fundamental problems related to geometric packing and covering, and design algorithms with improved worst-case performance guarantees for them. These problems have numerous applications in resource allocation, logistics, packing, and sensor networks.

First, we study the Strip Packing problem (SP), where we are given a vertical half-strip \left[0,W\right]\times\left[0,\infty\right) and a set of n axis-aligned rectangles of width at most W . The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this thesis, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and makespan minimization on identical machines, and thus it is already strongly NP-Hard. Moreover, it is NP-Hard to obtain a polynomial-time \left(3/2\ -\ \epsilon\right)-approximation algorithm for GSP for any \epsilon>\ 0 (exactly as Strip Packing). We provide a matching polynomial time \left(3/2+\epsilon\right)-approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time \left(3/2+\epsilon\right)-approximation algorithm for GSP. This is surprising as it is NP-Hard to obtain a \left(5/4\ -\ \epsilon\right)-approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.

In the context of covering, we study the geometric versions of Set Cover and the related dual Hitting Set problem, and present online and dynamic algorithms for them. In the online version of Set Cover (resp. Hitting Set), m sets (resp. n points) are given and n points (resp. m sets) ar- rive online, one-by-one. In the dynamic versions, points (resp. sets) can arrive as well as depart. Our goal as before is to maintain a set cover (resp. hitting set), minimizing the size of the computed solution. For online set cover for axis-parallel squares of arbitrary sizes, we present a tight O\left(\log{n}\right)-competitive algorithm, improving upon the O\left(\log{n}\log{m}\right) general case guarantee. In the same setting for hitting set, we provide a tight O(\log\funcapply N)\ -competitive algorithm, assuming that all points have integral coordinates in \left[0,N\right)^2. No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems). For both dynamic set cover and hitting set with d dimensional hyperrectangles, we obtain \left(\log{m}\right)^{O\left(d\right)}-approximation algorithms with \left(\log{m}\right)^{O\left(d\right)} worst-case update time. This partially answers an open question posed by Chan et al. [SODA’22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an extended quad-tree approach and a frequency reduction technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.