1 citations · 1 across the 6 of their papers we have counts for
8 papers
Pack, Remove, Reserve -- Online Knapsack with Second Thoughts
Hans-Joachim Böckenhauer, Dennis Komm, Emanuel Skodinis +2
We study the online proportional knapsack problem with two paid forms of recourse. Items arrive one by one and must be handled immediately, without knowledge of the future: an algo…
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…
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…
Tree Coloring: Random Order and Predictions
Fabian Frei, Matthias Gehnen, Dennis Komm +4
Coloring is a notoriously hard problem, and even more so in the online setting, where each arriving vertex has to be colored immediately and irrevocably. Already on trees, which ar…
Finding Optimal Solutions With Neighborly Help
Elisabet Burjons, Fabian Frei, Edith Hemaspaandra +2
Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficientl…
Advice Complexity of the Online Search Problem
Jhoirene Clemente, Juraj Hromkovic, Dennis Komm +1
The online search problem is a fundamental problem in finance. The numerous direct applications include searching for optimal prices for commodity trading and trading foreign curre…