2 papers
cs.CC2025
Hardness of SetCover Reoptimization
Klaus Jansen, Tobias Mömke, Björn Schumacher
We study hardness of reoptimization of the fundamental and hard to approximate SetCover problem. Reoptimization considers an instance together with a solution and a modified instan…
cs.DS2024
Convolution and Knapsack in Higher Dimensions
Kilian Grage, Klaus Jansen, Björn Schumacher
In the Knapsack problem, one is given the task of packing a knapsack of a given size with items in order to gain a packing with a high profit value. An important connection to the…