BARC talk by Arindam Khan

Wednesday, 19 June 2024, Arindam Khan, Associate professor at the Indian Institute of Science, Bangalore, India, will give a talk on "Recent Trends in Rectangle Packing and Covering".

Rectangle packing and covering problems are of paramount importance in many industrial applications, from cutting stock to VLSI design to logistics. These problems are also a natural generalization of classical NP-hard problems such as bin packing and knapsack problems. Thus rectangle packing and covering has also been studied extensively from a theoretical viewpoint and is one of the central areas of research in approximation algorithms, online algorithms, dynamic algorithms, and computational geometry.
In this talk, Arindam will focus on the recent trends in approximation algorithms for rectangle packing and covering, especially their work on problems such as maximum independent set of rectangles [SODA’22, APPROX’20], geometric knapsack [FOCS’17, SOCG’21, ICALP’22],  geometric bin packing [SODA’14, APPROX’21, FSTTCS’22], two-dimensional strip packing [APPROX’21, ICALP’22, APPROX’20], unsplittable flow on a path [ESA’22], rectangle set cover [SoCG’23], rectangle stabbing [IPCO’22], etc.

Portrait of Arindam KhanBio:
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.

Mikkel Abrahamsen