Generalized Sorting with Predictions

Pinyan Lu, Xuandi Ren, Enze Sun +1

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^…