BARC talk by Arindam Khan 2025

Tuesday, May 13, 2025, Arindam Khan, Associate Professor at the Indian Institute of Science, Bangalore, India, will give a talk on "Improved Approximation Algorithms for Three-Dimensional Packing".

Abstract:
Three-dimensional (3D) packing problems are fundamental in computer science, combinatorial optimization, and discrete geometry. Despite its omnipresence in logistics and cutting industry, there is little progress in the past decade in the approximability for these problems due to their inherent intractability. In this talk, I will mention our recent results that have given improved approximation guarantees for four classical packing problems — 3D Knapsack, 3D Bin Packing (3D-BP), 3D Strip Packing (3D-SP), and Minimum Volume Bounding Box (3D-MVBB). 

In 3D Knapsack, we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thole, and Thomas (2008), who gave a (7 + ε)-approximation algorithm. We provide an improved 4.79-approximation algorithm.
This is a joint work with Klaus Jansen, Debajyoti Kar, KVN Sreenivas, and Malte Tutas. 

In the other three problems, 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-SP, we need to pack them into a 3D cuboid with a unit square base and minimum height. Finally, in 3D-MVBB, the goal is to pack 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 and 3D-SP. The previous best (absolute) approximation for all three problems is by Li and Cheng (1990), who gave algorithms with approximation ratios of 13, 46/7, and 46/7+ε, respectively, for 3D-BP, 3D-SP, and 3D-MVBB. We provide improved approximation ratios of 6, 6, and 3+ε, respectively, for the three problems, for any constant ε>0.
For 3D-BP, in the asymptotic regime, Caprara (2008) gave an asymptotic approximation ratio of 2.86. We provide an algorithm with an improved asymptotic approximation ratio of 2.54.

Joint work with Debajyoti Kar and Malin Rau. 

Bio:
Arindam Khan is an Associate Professor at Indian Institute of Science, Bengaluru. He received his PhD in Algorithms, Combinatorics, and Optimization (Computer Science) from Georgia Institute of Technology, Atlanta. He received his BTech and MTech from Indian Institute of Technology (IIT), Kharagpur. His research interests are in approximation/online algorithms, computational geometry and theoretical machine learning. He is a recipient of Google India Research Award, Prof. Priti Shankar Teaching Award, MFCS’20 Best Paper Award, and Pratiksha Trust Young Investigator Award.

Host:
Mikkel Vind Abrahamsen