Universal Sorting: Finding a DAG using Priced Comparisons

We resolve two open problems in sorting with priced information, introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparisons have different (potentially infinite) costs. The goal is to sort with small competitive ratio (algorithmic cost divided by cheapest proof). 1) When all costs are in $\{0,1,n,\infty\}$, we give an algorithm that has $\widetilde{O}(n^{3/4})$ competitive ratio. Our algorithm generalizes the algorithms for generalized sorting (all costs are either $1$ or $\infty$), a version initiated by [Huang, Kannan, Khanna, FOCS 2011] and addressed recently by [Kuszmaul, Narayanan, FOCS 2021]. 2) We answer the problem of bichromatic sorting posed by [CFGKRS]: The input is split into $A$ and $B$, and $A-A$ and $B-B$ comparisons are more expensive than an $A-B$ comparisons. We give a randomized algorithm with a O(polylog n) competitive ratio. These results are obtained by introducing the universal sorting problem, which generalizes the existing framework in two important ways. We remove the promise of a directed Hamiltonian path in the DAG of all comparisons. Instead, we require that an algorithm outputs the transitive reduction of the DAG. For bichromatic sorting, when $A-A$ and $B-B$ comparisons cost $\infty$, this generalizes the well-known nuts and bolts problem. We initiate an instance-based study of the universal sorting problem. Our definition of instance-optimality is inherently more algorithmic than that of the competitive ratio in that we compare the cost of a candidate algorithm to the cost of the optimal instance-aware algorithm. This unifies existing lower bounds, and opens up the possibility of an $O(1)$-instance optimal algorithm for the bichromatic version.