10 citations · 31 across the 24 of their papers we have counts for
31 papers · 1 filter
A Consistency-Robustness Framework for Robust Optimization: Integrating Predictions into Robust Scheduling
Yasser Alghouass, Eric Balkanski, Vineet Goyal +1
Robust optimization protects against uncertainty by optimizing for the worst case over a prescribed uncertainty set. This protection can be overly conservative when forecasts, hist…
Santa Claus meets Makespan and Matroids: Algorithms and Reductions
Étienne Bamas, Alexander Lindermayr, Nicole Megow +2
In this paper we study the relation of two fundamental problems in scheduling and fair allocation: makespan minimization on unrelated parallel machines and max-min fair allocation,…
Recoverable Robust Optimization with Commitment
Felix Hommelsheim, Nicole Megow, Komal Muluk +1
We propose a model for recoverable robust optimization with commitment. Given a combinatorial optimization problem and uncertainty about elements that may fail, we ask for a robust…
Sorting and Hypergraph Orientation under Uncertainty with Predictions
Thomas Erlebach, Murilo Santos de Lima, Nicole Megow +1
Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of unce…
Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary
Alexander Lindermayr, Nicole Megow, Martin Rapp
We consider online scheduling on unrelated (heterogeneous) machines in a speed-oblivious setting, where an algorithm is unaware of the exact job-dependent processing speeds. We sho…
Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints
Alexandra Lassota, Alexander Lindermayr, Nicole Megow +1
We consider non-clairvoyant scheduling with online precedence constraints, where an algorithm is oblivious to any job dependencies and learns about a job only if all of its predece…
Matching Augmentation via Simultaneous Contractions
Mohit Garg, Felix Hommelsheim, Nicole Megow
We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a -edge-connected spanning subgraph by adding the minimum number of ed…
Set Selection under Explorable Stochastic Uncertainty via Covering Techniques
Nicole Megow, Jens Schlöter
Given subsets of uncertain values, we study the problem of identifying the subset of minimum total value (sum of the uncertain values) by querying as few values as possible. This s…
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…
Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
Thomas Erlebach, Murilo Santos de Lima, Nicole Megow +1
We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number…
A Universal Error Measure for Input Predictions Applied to Online Graph Problems
Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela +3
We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a ge…
Permutation Predictions for Non-Clairvoyant Scheduling
Alexander Lindermayr, Nicole Megow
In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements with the objective to minimize the total (we…
Orienting (hyper)graphs under explorable stochastic uncertainty
Evripidis Bampis, Christoph Dürr, Thomas Erlebach +3
Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node wit…
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…
Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice
Bertrand Simon, Joachim Falk, Nicole Megow +1
Static (offline) techniques for mapping applications given by task graphs to MPSoC systems often deliver overly pessimistic and thus suboptimal results w.r.t. exploiting time slack…
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…
Optimal Algorithms for Scheduling under Time-of-Use Tariffs
Lin Chen, Nicole Megow, Roman Rischke +2
We consider a natural generalization of classical scheduling problems in which using a time unit for processing a job causes some time-dependent cost which must be paid in addition…
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…
An Adversarial Model for Scheduling with Testing
Christoph Dürr, Thomas Erlebach, Nicole Megow +1
We introduce a novel adversarial model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown am…
Scheduling Maintenance Jobs in Networks
Fidaa Abed, Lin Chen, Yann Disser +5
We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focu…