[Talks@IDSIA] PIDSIA Seminar by Waldo Gálvez (22nd of October)
*Title:
Approximation Algorithms for Two-dimensional Geometric Packing Problems
*Abstract:
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.
*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.
*Date:
Tuesday, 22nd of October 2019, 12:00-13:00
*Location:
Manno, Galleria 1, 2nd floor, room G1-204
*Doodle 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