Professor Thomas Erlebach thomas.erlebach@durham.ac.uk
Professor Computer Science
Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
Erlebach, Thomas; de Lima, Murilo Santos; Megow, Nicole; Schlöter, Jens
Authors
Murilo Santos de Lima
Nicole Megow
Jens Schlöter
Contributors
Shiri Chechik
Editor
Gonzalo Navarro
Editor
Eva Rotenberg
Editor
Grzegorz Herman
Editor
Abstract
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.
Citation
Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2022). Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms (ESA 2022) (12:1-12:16). https://doi.org/10.4230/lipics.esa.2022.12
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 |
Volume | 244 |
Pages | 12:1-12:16 |
Series Title | LIPIcs |
Book Title | 30th Annual European Symposium on Algorithms (ESA 2022) |
DOI | https://doi.org/10.4230/lipics.esa.2022.12 |
Public URL | https://durham-repository.worktribe.com/output/1136694 |
Publisher URL | https://algo2022.eu/esa/ |
Related Public URLs | https://arxiv.org/abs/2206.15201 |
Files
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
You might also like
Sorting and Hypergraph Orientation under Uncertainty with Predictions
(2023)
Presentation / Conference Contribution
Package Delivery Using Drones with Restricted Movement Areas
(2022)
Presentation / Conference Contribution
Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty
(2021)
Presentation / Conference Contribution
Parameterized temporal exploration problems
(2022)
Presentation / Conference Contribution
Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
(2021)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
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 © 2024
Advanced Search