10 citations · 31 across the 24 of their papers we have counts for
5 papers · 1 filter
Learning-Augmented Query Policies
Thomas Erlebach, Murilo S. de Lima, Nicole Megow +1
We study how to utilize (possibly machine-learned) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. The goal is to minimize the…
Speed-Robust Scheduling -- Sand, Bricks, and Rocks
Franziska Eberle, Ruben Hoeksma, Nicole Megow +3
The speed-robust scheduling problem is a two-stage problem where given machines, jobs must be grouped into at most bags while the processing speeds of the given machine…
Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time
Franziska Eberle, Nicole Megow, Lukas Nölke +2
Knapsack problems are among the most fundamental problems in optimization. In the Multiple Knapsack problem, we are given multiple knapsacks with different capacities and items wit…
On Hop-Constrained Steiner Trees in Tree-Like Metrics
Martin Böhm, Ruben Hoeksma, Nicole Megow +2
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint which requires the depth of the tree to be at most . Our main result is an exact algor…
Online Minimum Cost Matching on the Line with Recourse
Nicole Megow, Lukas Nölke
In online minimum cost matching on the line, requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The…