2 papers
cs.CC2025
Hardness of SetCover Reoptimization
Klaus Jansen, Tobias Mömke, Tobias Mömke +2
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.DS2025
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…