# Sorting and Hypergraph Orientation under Uncertainty with Predictions

arXiv: https://arxiv.org/abs/2305.09245 · HTML: https://mlsanity.com/paper/2305.09245/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 55 references that are in the map.
- First posted on arXiv 16 May 2023.

## Builds on (most cited first, 18 of 18)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Online Graph Algorithms with Predictions](https://mlsanity.com/paper/2112.11831/) (2021)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Distortion-Oblivious Algorithms for Minimizing Flow Time](https://mlsanity.com/paper/2109.08424/) (2021)
- [Semi-Online Bipartite Matching](https://mlsanity.com/paper/1812.00134/) (2018)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Robustification of Online Graph Exploration Methods](https://mlsanity.com/paper/2112.05422/) (2021)
- [Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty](https://mlsanity.com/paper/2206.15201/) (2022)
- [An Adversarial Model for Scheduling with Testing](https://mlsanity.com/paper/1709.02592/) (2017)
- [The minimum cost query problem on matroids with uncertainty areas](https://mlsanity.com/paper/1904.11668/) (2019)
- [Explorable Uncertainty in Scheduling with Non-Uniform Testing Times](https://mlsanity.com/paper/2009.13316/) (2020)
- [Query-Competitive Sorting with Uncertainty](https://mlsanity.com/paper/2012.09475/) (2020)
- [Query Minimization under Stochastic Uncertainty](https://mlsanity.com/paper/2010.03517/) (2020)
- [Scheduling with Testing on Multiple Identical Parallel Machines](https://mlsanity.com/paper/2105.02052/) (2021)
- [Orienting (hyper)graphs under explorable stochastic uncertainty](https://mlsanity.com/paper/2107.00572/) (2021)

## Built on by (most cited first, 2 of 2)

- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Accelerating Matroid Optimization through Fast Imprecise Oracles](https://mlsanity.com/paper/2402.02774/) (2024)

## Abstract (arXiv)

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 hypergraph orientation, for any γ ≥ 2, we give an algorithm that achieves a competitive ratio of 1+1/γ for correct predictions and γ for arbitrarily wrong predictions. For sorting, we achieve an optimal solution for accurate predictions while still being 2-competitive 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.