Seminars

View all Seminars  |  Download ICal for this event

Advances in Approximation Algorithms for Geometric Packing and Separation

Series: Ph.D. Thesis Defense

Speaker: Debajyoti Kar, Ph.D (Engg.) student, Dept. of CSA

Date/Time: Nov 13 16:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Faculty Advisor: Prof. Arindam Khan & Prof. Siddharth Barman

Abstract:
Approximation algorithms play a central role in tackling computationally intractable optimization problems that arise in geometry, logistics, scheduling, and resource allocation. This thesis develops new algorithmic and structural techniques for a range of geometric optimization problems, with a particular emphasis on multidimensional packing, online scheduling, and geometric separation.\n\nThe first part of the thesis studies approximation algorithms for geometric packing problems. We begin with the two-dimensional geometric knapsack problem with orthogonal rotations, in which we are given a square knapsack and a set of rectangles with associated profits. The objective is to find a maximum profit subset of rectangles that can be packed without overlap in an axis-aligned manner, possibly by rotating some rectangles by $90^{\\circ}$. We resolve a long-standing open problem by presenting the first polynomial-time approximation scheme (PTAS) for the cardinality version of the problem, i.e., when all rectangles have identical profits. This improves upon the previous $4/3+\\varepsilon$ approximation due to G\\alvez, Grandoni, Heydrich, Ingala, Khan and Wiese (FOCS 2017). Our approach is based on a new \\emph{resource contraction lemma} and an improved structural characterization showing that there exist near-optimal packings using only a constant number of simple rectangular containers, referred to as \\emph{container packings}. In contrast, for the general weighted case, we prove that this simple type of packing is not sufficient to obtain a better approximation ratio than $1.5$. However, we break this structural barrier and design a $(1.497+\\varepsilon)$-approximation algorithm in the weighted case. Finally, we establish a lower bound of $n^{\\Omega(1/\\varepsilon)}$ on the running time of any $(1+\\varepsilon)$-approximation algorithm for our problem even in the cardinality setting, assuming the $k$-\\textsc{Sum} Conjecture.\n\nWe next investigate approximation algorithms for three-dimensional packing problems. In the three-dimensional knapsack problem, the input consists of a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack, and the objective is to compute a maximum-profit subset of cuboids that admits a non-overlapping packing inside the knapsack. Our main contribution is a generalization of the framework of container packings to the three-dimensional setting. This leads to improved polynomial-time approximation algorithms with guarantees of $139/29+\\varepsilon\\approx 4.794$ when rotations are not allowed and $30/7+\\varepsilon\\approx 4.286$ when rotations by $90^\\circ$ are permitted. These improve upon the previous best approximation ratios of $7+\\varepsilon$ and $5+\\varepsilon$, respectively, due to Diedrich, Harren, Jansen, Th{\\\"{o}}le, and Thomas (TAMC 2008). \n\nNext, we consider the three-dimensional bin packing problem, where again the input consists of a set of axis-aligned cuboids, and the objective is to find an axis-aligned non-overlapping packing of all cuboids using the minimum number of unit cube bins. In the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math.~Oper.~Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) for the problem even when all items have the same height. Caprara (Math.~Oper.~Res., 2008) gave an asymptotic approximation ratio of $T_{\\infty}^2 + \\varepsilon\\approx 2.86$, where $T_{\\infty}$ is the well-known Harmonic constant in bin packing. We improve this to an asymptotic approximation ratio of $3 T_{\\infty}/2 +\\eps \\approx 2.54$, and also obtain an improved absolute approximation ratio of $6$ for three-dimensional bin packing. We further extend our techniques to the three-dimensional minimum volume bounding box problem, where the objective is to pack all input cuboids into an axis-aligned cuboid of minimum volume. We give an absolute $3+\\varepsilon$ approximation algorithm and show that, in contrast to three-dimensional bin packing, this problem admits an asymptotic polynomial-time approximation scheme (APTAS). \n\nThe thesis next considers geometric optimization under uncertainty through the maximum independent set problem for $d$-dimensional hyperrectangles. Although polynomial-time $(\\log n)^{O(d)}$-approximation algorithms are known in the offline setting, the problem becomes significantly more challenging in the online setting, where input hyperrectangles arrive one by one in an adversarial order. Even for interval scheduling, an $\\Omega(n)$ lower bound is known on the competitive ratio. To circumvent these challenges, we consider the random-order arrival model, where the input objects arrive in uniformly random order. We show that perhaps surprisingly, in this model, the problem admits approximation guarantees that nearly match the best-known offline algorithms, up to polylogarithmic factors. In particular, we present a simple $(\\log n)^{O(d)}$-competitive algorithm for $d$-dimensional hyperrectangles that runs in $\\tilde{O_d}(n)$ time. Our framework further extends to more general classes of geometric objects, including $d$-dimensional fat objects and ellipsoids, yielding $(\\log n)^{O(d)}$-competitive algorithms for these settings as well. \n\nFinally, we resolve a longstanding open problem posed by Urrutia (1996), known as the \\emph{glass cutting} problem. We show that every family of pairwise disjoint arbitrarily-sized fat convex objects contains a linearly large subset that can be recursively separated by guillotine cuts. We introduce the framework of \\emph{doubly-random hierarchical grids} which also yields improved quantitative guarantees for important special cases, including disks and axis-aligned squares. For axis-aligned squares with axis-aligned guillotine cuts, we leverage additional structural properties of squares to show that at least $13.46\\%$ of the squares are separable, improving the previous best bound of $9/256 \\approx 3.51\\%$ due to Chalermsook, Kugelmann, Orgo, Uniyal, and Zarsav~(WADS 2025). For disks, by exploiting Olers packing inequality, we prove that at least $n/93$ disks can always be separated. \n\nOverall, this thesis introduces several new structural techniques -- including resource contraction, multidimensional container packings, and randomized hierarchical decompositions -- that lead to improved approximation algorithms and resolve multiple longstanding open problems in geometric optimization.\n\nTeams link: Link