Tight Bounds for Sorting Under Partial Information

Sorting is one of the fundamental algorithmic problems in theoretical computer science. It has a natural generalization, introduced by Fredman in 1976, called sorting under partial information. The input consists of: –a ground set$X$of size$n$, –a partial oracle$O_{F}$(where partial oracle queries for any$(x_{i},x_{j})$output whether$x_{i}\prec _{P}x_{j}$, for some partial order$P$), –a linear oracle$O_{L}$(where linear oracle queries for any$(x_{i},x_{j})$output whether$x_{i} < _{L}x_{j}$and the order$L$extends$P$) The goal is to recover the linear order$L$on$X$using the fewest number of linear oracle queries. In this problem, we measure algorithmic complexity through three metrics: the number of linear oracle queries to$O_{L}$, the number of partial oracle queries to$O_{P}$, and the time spent (the number of algorithmic instructions required to identify for which pairs$(x_{i},x_{j})$a partial or linear oracle query is performed). Let$e(P)$denote the number of linear extensions of$P$. Any algorithm requires worst-case$\log_{2}e(P)$linear oracle queries to recover the linear order on$X$. In 1984, Kahn and Saks presented the first algorithm that uses$\Theta(\log e(P))$linear oracle queries (using$O(n^{2})$partial oracle queries and exponential time). Since then, both the general problem and restricted variants have been consistently studied. The state-of-the-art for the general problem is by Cardinal, Fiorini, Joret, Jungers and Munro who at STOC'10 manage to separate the linear and partial oracle queries into a preprocessing and query phase. They can preprocess$P$using$O(n^{2})$partial oracle queries and$O(n^{2.5})$time. Then, given$O_{L}$, they uncover the linear order on$X$in$\Theta(\log e(P)$linear oracle queries and$O(n+\log e(P))$time - which is worst-case optimal in the number of linear oracle queries but not in the time spent. We present the first algorithm that uses a subquadratic number of partial oracle queries. For any constant$c\geq 1$, our algorithm can preprocess$O_{F}$using O$O(n^{1+\frac{1}{c}})$partial oracle queries and time. Given${OL}$, we uncover the linear order on$X$using$\Theta(c\log e(P))$linear oracle queries and time, which is worst-case optimal. We show a matching lower bound for the prepossessing also, as we show that there exist positive constants$((y,\beta)$where for any constant$c\geq 3$, any algorithm that uses at most$\alpha\cdot n^{1+\frac{1}{c}}$partial oracle queries must use worst-case at least$\beta\cdot c\log e(P)$linear oracle queries. Thus, we solve the problem of sorting under partial information through an algorithm that is asymptotically tight across all three metrics.