2 citations · 3 across the 5 of their papers we have counts for
6 papers
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 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…
Delaying Decisions and Reservation Costs
Elisabet Burjons, Fabian Frei, Matthias Gehnen +3
We study the Feedback Vertex Set and the Vertex Cover problem in a natural variant of the classical online model that allows for delayed decisions and reservations. Both problems c…
Advice Complexity bounds for Online Delayed F-Node-, H-Node- and H-Edge-Deletion Problems
Niklas Berndt, Henri Lotze
Let F be a fixed finite obstruction set of graphs and G be a graph revealed in an online fashion, node by node. The online Delayed F-Node-Deletion Problem (F-Edge-Deletion Problem}…
The Slotted Online One-Sided Crossing Minimization Problem on 2-Regular Graphs
Elisabet Burjons, Janosch Fuchs, Henri Lotze
In the area of graph drawing, the One-Sided Crossing Minimization Problem (OSCM) is defined on a bipartite graph with both vertex sets aligned parallel to each other and all edges…
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…