Abstract
Rectangle packing and covering problems are of paramount importance in many industrial applications, from logistics and cutting stock to VLSI design. 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/online/dynamic/parameterized algorithms, combinatorial optimization, and computational geometry. In this talk, we will focus on the recent trends in approximation algorithms for rectangle packing and covering, especially our recent work on problems such as maximum independent set of rectangles [SODA’22, APPROX’20, ESA'24], geometric knapsack [FOCS’17, SOCG’21, ICALP’22, ICALP'24, SOCG'25], geometric bin packing [SODA’14, APPROX’21, SOCG'25], strip packing [APPROX’21, ICALP’22, APPROX’20], etc.
