9 papers
The Secretary Problem with a Stochastic Precursor
Franziska Eberle, Alexander Lindermayr
In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that pre…
Scheduling on a Stochastic Number of Machines
Moritz Buchem, Franziska Eberle, Hugo Kooki Kasuya Rosado +2
We consider a new scheduling problem on parallel identical machines in which the number of machines is initially not known, but it follows a given probability distribution. Only af…
Accelerating Matroid Optimization through Fast Imprecise Oracles
Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr +3
Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus…
Configuration Balancing for Stochastic Requests
Franziska Eberle, Anupam Gupta, Nicole Megow +2
The configuration balancing problem with stochastic requests generalizes many well-studied resource allocation problems such as load balancing and virtual circuit routing. In it, w…
Robustification of Online Graph Exploration Methods
Franziska Eberle, Alexander Lindermayr, Nicole Megow +2
Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. We initiate the study of a learning-augmented v…
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…
Online Throughput Maximization on Unrelated Machines: Commitment is No Burden
Franziska Eberle, Nicole Megow, Kevin Schewior
We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a fea…
A general framework for handling commitment in online throughput maximization
Lin Chen, Franziska Eberle, Nicole Megow +2
We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-serve…