Seminars

View all Seminars  |  Download ICal for this event

Algorithms for geometric packing and covering problems

Series: M.Tech (Research) Thesis Defense -ON-LINE

Speaker: Aditya Abhay Lonkar M.Tech (Research) student Depart. of C.S.A

Date/Time: Aug 28 16:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor: Dr. Arindam Khan

Abstract:
We study fundamental geometric packing and covering problems and design algorithms with improved worst-case guarantees for them under various paradigms. In particular, we study the Strip Packing problem (SP), where we are given a vertical
half-strip $[0,W]times[0,infty)$ 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 paper, 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 $mathsf{NP}$-hard. Moreover, due to a reduction from the Partition problem, it is $mathsf{NP}$-hard to obtain a polynomial-time $(3/2-epsilon)$-approximation algorithm for GSP for any $epsilon>0$ (exactly as Strip Packing). We provide a matching polynomial time $(3/2+epsilon)$-approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time $(1+epsilon)$-approximation algorithm for GSP.
This is surprising as it is $mathsf{NP}$-hard to obtain a $(5/4-epsilon)$-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 Set Cover and the related dual Hitting Set problem, which are fundamental problems in combinatorial optimization. They are well-studied in the offline, online, and dynamic settings. In the offline version of set cover, $n$ elements from a universe $U$ and a set collection $mathcal{F}subseteq 2^U$ are given as input. The objective is to choose a minimum cardinality subcollection $mathcal{F} $ of $mathcal{F}$ such that all the elements are covered. This problem is known to be $mathsf{NP}$-hard to even approximate beyond $(1-epsilon)log n$ for a fixed $epsilon>0$. 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. We study the geometric versions of these problems, where the sets are geometric objects and the elements are points in a fixed euclidean space, and present new online and dynamic algorithms for them.

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 nlog 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. [SODA22]. 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.

Microsoft teams link:


Link