10 citations · 31 across the 24 of their papers we have counts for
36 papers
Online Fair Division under Eligibility Constraints
Joes Biburger, Nicole Megow, Golnoosh Shahkarami
We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assig…
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…
On Solution Discovery via Reconfiguration
Michael R. Fellows, Mario Grobler, Nicole Megow +5
The dynamics of real-world applications and systems require efficient methods for improving infeasible solutions or restoring corrupted ones by making modifications to the current…
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…
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…
On Complexity of 1-Center in Various Metrics
Amir Abboud, Mohammad Hossein Bateni, Vincent Cohen-Addad +2
We consider the classic 1-center problem: Given a set of points in a metric space find the point in that minimizes the maximum distance to the other points of . We s…
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…
Double Coverage with Machine-Learned Advice
Alexander Lindermayr, Nicole Megow, Bertrand Simon
We study the fundamental online k-server problem in a learning-augmented setting. While in the traditional online model, an algorithm has no information about the request sequence,…
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…