Algorithms for geometric packing and covering problems

includes bibliographical references and index

MTech(Res); 2023; Computer Science and Automation

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
[0, W] × [0,∞) 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 also makespan minimization on identical machines, and
thus it is already strongly NP-Hard. Moreover, it is NP-Hard to obtain a polynomial-time
(3/2 − ε)-approximation algorithm for GSP for any ε > 0 (exactly as Strip Packing). We
provide a matching polynomial time (3/2 + ε)-approximation algorithm for GSP. Furthermore,
we present a pseudo-polynomial time (1+ε)-approximation algorithm for GSP. This is surprising
as it is NP-Hard to obtain a (5/4 − ε)-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) arrive 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(log n)-competitive algorithm, improving upon the O(log n log m) general case guarantee. In the same setting for hitting set, we provide a tight O(log N)-competitive algorithm, assuming
that all points have integral coordinates in [0, N)
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 (log m)
O(d)
-approximation algorithms with (log m)
O(d) 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 quadtree approach and a frequency reduction technique that reduces geometric set cover instances
to instances of general set cover with bounded frequency.