10 citations · 31 across the 24 of their papers we have counts for
6 papers · 1 filter
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…