2026-07-22T12:15:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16987 2024-03-06T10:58:54Z ddc:004 open_access

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty Erlebach, Thomas de Lima, Murilo Santos Megow, Nicole Schlöter, Jens explorable uncertainty queries untrusted predictions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Erlebach and Murilo Santos de Lima and Nicole Megow and Jens Schlöter 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.49 urn:nbn:de:0030-drops-169872 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.49 eng https://creativecommons.org/licenses/by/4.0/legalcode