We study the two-dimensional (geometric) knapsack problem with rotations (2DKR), 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∘. The best-known polynomial time algorithm for the problem has an approximation ratio of 3/2+є for any constant є>0, with an improvement to 4/3+є in the cardinality case, due to Gálvez, Grandoni, Heydrich, Ingala, Khan, and Wiese (FOCS 2017, TALG 2021). Obtaining a PTAS for the problem, even in the cardinality case, has remained a major open question in the setting of multidimensional packing problems, as mentioned in the survey by Christensen, Khan, Tetali, and Pokutta (Computer Science Review, 2017).

We study two fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), and 3D Minimum Volume Bounding Box (3D-MVBB), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3D-BP, we need to pack the given cuboids into the minimum number of unit cube bins. In 3D-MVBB, the goal is to pack them into a cuboid box of minimum volume. It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin -- giving an (absolute) approximation hardness of $2$ for 3D-BP. The previous best (absolute) approximation for both the problems follows from a result of Buchwald and Scheithauer (Int.~Trans.~Oper.~Res., 2016), yielding approximation ratios of $11$, and $5+\varepsilon$, respectively, for 3D-BP and 3D-MVBB. We provide improved approximation ratios of $6$, and $3+\varepsilon$, respectively, for the two problems, for any constant $\varepsilon > 0$. For 3D-BP, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math.~Oper.~Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) 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 provide an algorithm with an improved asymptotic approximation ratio of $3T_{\infty}/2 +\varepsilon \approx 2.54$. Further, we show that unlike 3D-BP, 3D-MVBB admits an APTAS.

In the Maximum Independent Set of Hyperrectangles problem, we are given a set of $n$ (possibly overlapping) $d$-dimensional axis-aligned hyperrectangles, and the goal is to find a subset of non-overlapping hyperrectangles of maximum cardinality. For $d=1$, this corresponds to the classical Interval Scheduling problem, where a simple greedy algorithm returns an optimal solution. In the offline setting, for $d$-dimensional hyperrectangles, polynomial time $(\log n)^{O(d)}$-approximation algorithms are known. However, the problem becomes notably challenging in the online setting, where the input objects (hyperrectangles) appear one by one in an adversarial order, and on the arrival of an object, the algorithm needs to make an immediate and irrevocable decision whether or not to select the object while maintaining the feasibility. Even for interval scheduling, an $Ω(n)$ lower bound is known on the competitive ratio. To circumvent these negative results, in this work, we study the online maximum independent set of axis-aligned hyperrectangles in the random-order arrival model, where the adversary specifies the set of input objects which then arrive in a uniformly random order. Starting from the prototypical secretary problem, the random-order model has received significant attention to study algorithms beyond the worst-case competitive analysis. Surprisingly, we show that the problem in the random-order model almost matches the best-known offline approximation guarantees, up to polylogarithmic factors. In particular, we give a simple $(\log n)^{O(d)}$-competitive algorithm for $d$-dimensional hyperrectangles in this model, which runs in $\tilde{O_d}(n)$ time. Our approach also yields $(\log n)^{O(d)}$-competitive algorithms in the random-order model for more general objects such as $d$-dimensional fat objects and ellipsoids. Furthermore, our guarantees hold with high probability.

We study ROUND-UFP and ROUND-SAP, two generalizations of the classical BIN PACKING problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocation problem (SAP), respectively. We are given a path with capacities on its edges and a set of tasks where for each task we are given a demand and a subpath. In ROUND-UFP, the goal is to find a packing of all tasks into a minimum number of copies (rounds) of the given path such that for each copy, the total demand of tasks on any edge does not exceed the capacity of the respective edge. In ROUND-SAP, the tasks are considered to be rectangles and the goal is to find a non-overlapping packing of these rectangles into a minimum number of rounds such that all rectangles lie completely below the capacity profile of the edges. We show that in contrast to BIN PACKING, both the problems do not admit an asymptotic polynomial-time approximation scheme (APTAS), even when all edge capacities are equal. However, for this setting, we obtain asymptotic $(2+\varepsilon)$-approximations for both problems. For the general case, we obtain an $O(\log\log n)$-approximation algorithm and an $O(\log\log\frac{1}δ)$-approximation under $(1+δ)$-resource augmentation for both problems. For the intermediate setting of the no bottleneck assumption (i.e., the maximum task demand is at most the minimum edge capacity), we obtain absolute $12$- and asymptotic $(16+\varepsilon)$-approximation algorithms for ROUND-UFP and ROUND-SAP, respectively.