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.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne