direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Losing Weight is Easy

Dr. Stefan Kratsch (TU Berlin)

The talk discusses some aspects of having large numbers and weights in the inputs of combinatorial problems. Pivotal problems in this regard are Subset Sum and Knapsack but also weighted versions of classical NP-hard problems like Vertex Cover as well as problems related to integer linear programs. Shrinking numbers to small size is an important task in kernelization, where one studies provable bounds on efficient simplification of NP-hard problems.
We recall and lightly discuss some fairly recent attempts at coping with large numbers in Subset Sum and Knapsack. Further progress beyond these results was the topic of several open problems in kernelization. The last part of the talk shows how an almost 30 year old result defeats the open problems.

Joint work with Michael Etscheid, Matthias Mnich and Heiko Röglin (Universität Bonn).

Stefan Kratsch
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras