Sorting and Hypergraph Orientation under Uncertainty with Predictions
Thomas Erlebach Murilo Santos de Lima Nicole Megow Jens Schlöter
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 $\gamma \geq 2$, we
give an algorithm that achieves a competitive ratio of $1+1/\gamma$ for correct
predictions and $\gamma$ 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.