Professor Thomas Erlebach thomas.erlebach@durham.ac.uk
Professor Computer Science
Professor Thomas Erlebach thomas.erlebach@durham.ac.uk
Professor Computer Science
Murilo Santos de Lima
Nicole Megow
Jens Schlöter
Shiri Chechik
Editor
Gonzalo Navarro
Editor
Eva Rotenberg
Editor
Grzegorz Herman
Editor
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 of queries needed to solve the minimum spanning tree problem, a fundamental combinatorial optimization problem that has been central also to the research area of explorable uncertainty. For all integral γ≥2, we present algorithms that are γ-robust and (1+1γ)-consistent, meaning that they use at most γOPT queries if the predictions are arbitrarily wrong and at most (1+1γ)OPT queries if the predictions are correct, where OPT is the optimal number of queries for the given instance. Moreover, we show that this trade-off is best possible. Furthermore, we argue that a suitably defined hop distance is a useful measure for the amount of prediction error and design algorithms with performance guarantees that degrade smoothly with the hop distance. We also show that the predictions are PAC-learnable in our model. Our results demonstrate that untrusted predictions can circumvent the known lower bound of~2, without any degradation of the worst-case ratio. To obtain our results, we provide new structural insights for the minimum spanning tree problem that might be useful in the context of query-based algorithms regardless of predictions. In particular, we generalize the concept of witness sets -- the key to lower-bounding the optimum -- by proposing novel global witness set structures and completely new ways of adaptively using those.
Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2022, September). Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. Presented at 30th Annual European Symposium on Algorithms (ESA 2022), Potsdam, Germany
Presentation Conference Type | Conference Paper (published) |
---|---|
Conference Name | 30th Annual European Symposium on Algorithms (ESA 2022) |
Start Date | Sep 5, 2022 |
End Date | Sep 9, 2022 |
Acceptance Date | Jun 20, 2022 |
Publication Date | 2022 |
Deposit Date | Jul 4, 2022 |
Publicly Available Date | Jul 5, 2022 |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Peer Reviewed | Peer Reviewed |
Volume | 244 |
Pages | 49:1-49:18 |
Series Title | LIPIcs |
Book Title | 30th Annual European Symposium on Algorithms (ESA 2022) |
DOI | https://doi.org/10.4230/LIPIcs.ESA.2022.49 |
Public URL | https://durham-repository.worktribe.com/output/1136694 |
Publisher URL | https://algo2022.eu/esa/ |
Related Public URLs | https://arxiv.org/abs/2206.15201 |
Accepted Conference Proceeding
(695 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter;
licensed under Creative Commons License CC-BY 4.0
Parameterized temporal exploration problems
(2023)
Journal Article
Round-competitive algorithms for uncertainty problems with parallel queries
(2022)
Journal Article
Exploration of k-Edge-Deficient Temporal Graphs
(2022)
Journal Article
On the fast delivery problem with one or two packages
(2020)
Journal Article
Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings
(2022)
Journal Article
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search