TITLE: Algorithms for the Generalized Sorting Problem

Speaker: Zhiyi Huang, UPenn

Abstract:

We study the generalized sorting problem where we are given a set of $n$ 
elements to be sorted but only a subset of all possible pairwise element 
comparisons is allowed. The goal is to determine the sorted order using 
the smallest possible number of allowed comparisons. The generalized 
sorting problem may be equivalently viewed as follows. Given an 
undirected graph $G(V,E)$ where $V$ is the set of elements to be sorted 
and $E$ defines the set of allowed comparisons, adaptively find the 
smallest subset $E' \subseteq E$ of edges to probe such that the 
directed graph induced by $E'$ contains a Hamiltonian path.

When $G$ is a complete graph, we get the standard sorting problem, and 
it is well-known that $\Theta(n \log n)$ comparisons are necessary and 
sufficient. An extensively studied special case of the generalized 
sorting problem is the nuts and bolts problem where the allowed 
comparison graph is a complete bipartite graph between two equal-size 
sets. It is known that for this special case also, there is a 
deterministic algorithm that sorts using $\Theta(n \log n)$ comparisons. 
However, when the allowed comparison graph is arbitrary, to our 
knowledge, no bound better than the trivial $O(n^2)$ bound is known. Our 
main result is a randomized algorithm that sorts any allowed comparison 
graph using $O~(n^{3/2})$ comparisons with high probability (provided 
the input is sortable). We also study the sorting problem in randomly 
generated allowed comparison graphs, and show that when the edge 
probability is $p$, $O~(min{\frac{n}{p^2}, n^{3/2} \sqrt{p}})$ 
comparisons suffice on average to sort. This is joint work with Sampath 
Kannan and Sanjeev Khanna.