Generalized Sorting with Predictions

Abstract

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.

To appear in SOSA 2021