Campus Event Calendar

Event Entry

What and Who

The Frontiers of Packing

Karol Węgrzycki
Max-Planck-Institut für Informatik - D1
Joint Lecture Series
AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI  
Public Audience

Date, Time and Location

Wednesday, 8 May 2024
60 Minutes
E1 5


Packing problems are ubiquitous optimization problems in computer science, where the task is to pack some class of objects into some class of containers. Canonical examples of packing problems include Knapsack, Subset Sum, and Bin Packing, but also several graph problems can be expressed as packing problems.

Most packing problems are NP-hard, and thus are typically attacked by approximation algorithms and fixed-parameter tractability, the two most recognized algorithmic paradigms for dealing with NP-hardness in theoretical computer science. This talk surveys recent developments on these two perspectives for packing problems. More concretely, I will talk about the following flavours of packing:

- (packing in geometry): how to pack polygons on the plane.
- (packing numbers): how to pack items into a knapsack to maximize the value.
- (packing in vector addition systems): how to reach your destination without running out of gas and money.


Jennifer Müller
+49 681 9325 2900
--email hidden

Virtual Meeting Details

997 1565 5535
passcode not visible
logged in users only

Jennifer Müller, 04/03/2024 09:24 -- Created document.