Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty

Erlebach, Thomas; de Lima, Murilo Santos; Megow, Nicole; Schlöter, Jens

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