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…
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…
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…