Sorting and Hypergraph Orientation under Uncertainty with Predictions

Sorting and Hypergraph Orientation under Uncertainty with Predictions

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

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 5577-5585. https://doi.org/10.24963/ijcai.2023/619

Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of uncertain input elements can be obtained by a query and the goal is to minimize the number of queries needed to solve a problem. We study learning-augmented algorithms for sorting and hypergraph orientation under uncertainty, assuming access to untrusted predictions for the uncertain values. Our algorithms provide improved performance guarantees for accurate predictions while maintaining worst-case guarantees that are best possible without predictions. For sorting, our algorithm uses the optimal number of queries for accurate predictions and at most twice the optimal number for arbitrarily wrong predictions. For hypergraph orientation, for any γ≥2, we give an algorithm that uses at most 1+1/γ times the optimal number of queries for accurate predictions and at most γ times the optimal number for arbitrarily wrong predictions. These tradeoffs are the best possible. We also consider different error metrics and show that the performance of our algorithms degrades smoothly with the prediction error in all the cases where this is possible.
Keywords:
Search: S: Combinatorial search and optimisation
Planning and Scheduling: PS: Planning under uncertainty