3 papers
cs.DS2025
Forbidden Subgraph Problems with Predictions
Hans-Joachim Böckenhauer, Melvin Jahn, Dennis Komm +1
In the Online Delayed Connected H-Node-Deletion Problem, an unweighted graph is revealed vertex by vertex and it must remain free of any induced copies of a specific connected indu…
cs.DS2024
Online Unbounded Knapsack
Hans-Joachim Böckenhauer, Matthias Gehnen, Juraj HromkoviÄ +6
We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and…
cs.DS2024
Removable Online Knapsack and Advice
Hans-Joachim Böckenhauer, Fabian Frei, Peter Rossmanith
In the knapsack problem, we are given a knapsack of some capacity and a set of items, each with a size and a value. The goal is to pack a selection of these items fitting the knaps…