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
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 8 May 2024
12:15
60 Minutes
E1 5
002
Saarbrücken
Abstract
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.
Contact
Jennifer Müller
+49 681 9325 2900
--email hidden
Virtual Meeting Details
Zoom
997 1565 5535
passcode not visible
logged in users only
Jennifer Müller, 04/03/2024 09:24 -- Created document.