Seminars

View all Seminars  |  Download ICal for this event

Advances in Approximation Algorithms for Geometric Packing and Separation

Series: Ph.D. Colloquium

Speaker: Debajyoti Kar, Ph.D student, Dept. of CSA, IISc

Date/Time: Jul 16 11: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.

The 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 Galvez, 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.

We 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+varepsilonapprox 4.794$ when rotations are not allowed and $30/7+varepsilonapprox 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{