1 citations · 1 across the 6 of their papers we have counts for
7 papers
Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal
Matthias Gehnen, Kübra Güven, Moritz Stocker
We introduce the Online Unbounded Knapsack Problem with Removal, a variation of the well-known Online Knapsack Problem. Items, each with a weight and value, arrive online and an al…
Online Knapsack Problems with Estimates
Jakub Balabán, Matthias Gehnen, Henri Lotze +2
Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you…
Online General Knapsack with Reservation Costs
Elisabet Burjons, Matthias Gehnen
In the online general knapsack problem, an algorithm is presented with an item of size and value and must irrevocably choose to pack such an item into the knapsac…
Graph Exploration with Edge Weight Estimates
Matthias Gehnen, Ralf Klasing, Émile Naquin
In the Travelling Salesman Problem, every vertex of an edge-weighted graph has to be visited by an agent who traverses the edges of the graph. In this problem, it is usually assume…
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…