论文标题
通用分类带有预测
Generalized Sorting with Predictions
论文作者
论文摘要
Huang等人首先引入了广义分类问题，也称为禁止比较的分类。以及需要$ \ tilde o（n^{3/2}）$ probes的随机算法。我们研究了此问题，并对所有对允许比较作为输入的其他预测进行了其他预测。我们提出了一种随机算法，该算法使用$ o（n \ log n+w）$探针具有很高的概率和一种确定性算法，该算法使用$ o（nw）$ probes，其中$ w $是预测的错误数量。
Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. together with a randomized algorithm which requires $\tilde O(n^{3/2})$ probes. We study this problem with additional predictions for all pairs of allowed comparisons as input. We propose a randomized algorithm which uses $O(n \log n+w)$ probes with high probability and a deterministic algorithm which uses $O(nw)$ probes, where $w$ is the number of mistakes made by prediction.
