Waldo Gàlvez: Approximation Algorithms for Two-dimensional Geometric Packing Problems

22 October 2019

*Manno, Galleria 1, 2nd floor, room G1-204 @12h00*The field of Geometric Packing problems has attracted the attention of

many researchers in the late years. Generally speaking, in this

setting we are given a region in the two-dimensional plane and a set

of rectangles and the goal is to pack a subset of them inside the

given region in such a way that they do not overlap and some given

objective function is optimized. In this talk we will review our

recent developments on two of these problems in the framework of

Approximation Algorithms: Strip Packing and Geometric Knapsack. In the

first problem, the goal is to pack all the rectangles into a strip of

fixed width so as to minimize the final height of the packing, while

in the second one the goal is to pack a subset of the rectangles of

maximum profit into a rectangular region of fixed size. We will also

discuss applications and open questions regarding the mentioned

problems, the talk is meant to be accessible for non-experts.

many researchers in the late years. Generally speaking, in this

setting we are given a region in the two-dimensional plane and a set

of rectangles and the goal is to pack a subset of them inside the

given region in such a way that they do not overlap and some given

objective function is optimized. In this talk we will review our

recent developments on two of these problems in the framework of

Approximation Algorithms: Strip Packing and Geometric Knapsack. In the

first problem, the goal is to pack all the rectangles into a strip of

fixed width so as to minimize the final height of the packing, while

in the second one the goal is to pack a subset of the rectangles of

maximum profit into a rectangular region of fixed size. We will also

discuss applications and open questions regarding the mentioned

problems, the talk is meant to be accessible for non-experts.

## The speaker

Waldo Gálvez studied Applied Math at University of Chile and recently

got his PhD at IDSIA in the Algorithms and Complexity group. Starting

in January 2020, Waldo will join the Algorithms and Complexity group

at TU Munich as a postdoc. His main area of research is the design and

analysis of approximation algorithms, specially for Packing and

Network Design problems.

## Registration

Pizza (or alternative food) and drinks will be offered at the end of

the talk. If you plan to attend, please register in a timely fashion at the following link

so that we will have no shortage of food:

https://www.doodle.com/poll/pvqz8wvt6c3yvcei