5 citations · 10 across the 8 of their papers we have counts for
9 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…
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…
Zero-Memory Graph Exploration with Unknown Inports
Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger +1
We study a very restrictive graph exploration problem. In our model, an agent without persistent memory is placed on a vertex of a graph and only sees the adjacent vertices. The go…
Priority Algorithms with Advice for Disjoint Path Allocation Problems
Hans-Joachim Böckenhauer, Fabian Frei, Silvan Horvath
We analyze the Disjoint Path Allocation problem (DPA) in the priority framework. Motivated by the problem of traffic regulation in communication networks, DPA consists of allocatin…
Online Simple Knapsack with Reservation Costs
Hans-Joachim Boeckenhauer, Elisabet Burjons, Fabian Frei +3
In the online simple knapsack problem items are presented in an iterative fashion and an algorithm has to decide for each item whether to reject or permanently include it into the…
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…
Reoptimization of Parameterized Problems
Hans-Joachim Böckenhauer, Elisabet Burjons, Martin Raszyk +1
Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or ap…
The Graph Exploration Problem with Advice
Hans-Joachim Böckenhauer, Janosch Fuchs, Walter Unger
Moving an autonomous agent through an unknown environment is one of the crucial problems for robotics and network analysis. Therefore, it received a lot of attention in the last de…
Online Exploration of Rectangular Grids
Hans-Joachim Böckenhauer, Janosch Fuchs, Ulla Karhumäki +1
In this paper, we consider the problem of exploring unknown environments with autonomous agents. We model the environment as a graph with edge weights and analyze the task of visit…