No Polynomial Kernels for Knapsack

Orateur : Danny Hermelin
14 Mai 2024 à 14:00 ; lieu : Salle de séminaire 4B125 (bâtiment Copernic)

In this talk I will present a recent result regarding the non-existence of polynomial kernels for the knapsack parameter under two natural parameters: The number of different item profits, and the number of different item weights. The talk will not assume any prior knowledge on any of these concepts. The work presented is joint work with Klaus Heeger, Matthias Mnich, and Dvir Shabtay, and has been accepted to the next ICALP.


Salle de séminaire 4B125 (bâtiment Copernic)

5 Boulevard Descartes 77420 Champs-sur-Marne