Generalized Sorting with Predictions
Pinyan Lu, Xuandi Ren, Enze Sun, Yubo Zhang · Society for Industrial and Applied Mathematics eBooks · 2021
Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. [HKK11] together with a randomized algorithm which requires Õ(n3/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.