Logo Universität Bremen, back to home[Translate to English:]
Faculty 3 - Mathematics and Computer Science: Combinatorial Optimization and Logistics

Explorable Uncertainty

In explorable uncertainty we consider problems with uncertainty in numeric input parameters. In contrast to the other models for uncertainty, new information on the uncertain parts of the input does not arrive passively over time, but we can actively obtain new information by querying it. As queries are costly, the goal is to minimize the number of queries necessary to obtain sufficient information to solve the underlying optimization problem. 

As an example consider the minimum spanning tree problem under explorable uncertainty. In this problem, the edge weights are uncertain and we are only given an uncertainty interval for each edge that is guaranteed to contain the weight of the corresponding edge. Querying an edge reveals its weight. The goal is to minimize the number of queries necessary to obtain sufficient information to determine a minimum spanning tree.  As part of the project, we designed and analyzed randomized and learning augmented algorithms for MST under explorable uncertainty to improve upon the deterministic lower bound for the worst-case setting.

detective with magnifying glass
© pixabay

Publications on Explorable Uncertainty

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty arxiv.org
Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter
ESA 2022

Explorable Uncertainty Meets Decision-Making in Logistics springer.com 
Nicole Megow and Jens Schlöter
Dynamics in Logistics: 35-56, 2021  springer.com 

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty  pdf
Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter
Accepted for publication at ESA 2021

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
Jacob Focke, Nicole Megow, Julie Meißner
ACM Journal of Experimental Algorithmics 25(1), Article 1.14, 2020

An Adversarial Model for Scheduling with Testing
Christoph Dürr, Thomas Erlebach, Nicole Megow and Julie Meißner
Algorithmica 82(12): 3630-3675, 2020

Scheduling with Explorable Uncertainty  PDF  springer.com
C. Dürr, T. Erlebach, J. Meißner and N. Megow.
In Proc. of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 30:1-30:14, 2018.

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments  PDF
J. Focke, J. Meißner, N. Megow
In Proc. of the 16th International Symposium on Experimental Algorithms (SEA 2017), LIPIcs, Article No. 22; pp. 22:1–22:14, 2017.

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty  PDF
J. Meißner, N. Megow, M. Skutella
SIAM Journal on Computing 46(4): 1217-1240, 2017.

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty  PDF
J. Meißner, N. Megow and M. Skutella
In Proc. of the 23rd European Symposium on Algorithms (ESA 2015), LNCS 9294, pp. 878-890, Springer, 2015.

Updated by: Lukas Barning
RSS
Print page