Recent Trends in Rectangle Packing and Covering

Arindam Khan

Assistant Professor

Department of Computer Science & Automation

Indian Institute of Science

Bengaluru, India.

ABSTRACT

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, we will focus on the recent trends in approximation algorithms for rectangle packing and covering, especially our 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.

Speaker Bio: Arindam Khan is an Associate Professor at Indian Institute of Science, Bengaluru. He received his PhD in Algorithms, Combinatorics, and Optimization (Computer Science) and MS in Mathematics from Georgia Institute of Technology, Atlanta. He received his BTech and MTech from IIT Kharagpur. His research interests are in approximation/online algorithms, combinatorial optimization, theoretical machine learning, fairness, and computational geometry. 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.