5 citations · 10 across the 8 of their papers we have counts for
6 papers · 1 filter
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…