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.

该论文研究了在不确定性条件下，利用学习增强算法处理排序和超图方向问题，并提出了针对准确和错误预测的性能保证算法，可以通过查询提高不确定性元素的精确度，从而最小化问题求解所需的查询数量。