Sorting problems have long been one of the foundations of theoretical computer science. Sorting problems attempt to learn properties of an unknown total order of a known set. We test the order by comparing pairs of elements, and through repeated tests deduce some order structure on the set.
The set-maxima problem is: given a family S of subsets of a set X, produce the maximal element of each element of S. Local sorting is a sub-problem of set-maxima, when S is a subset of (X (choose) 2), i.e. there exists a graph G with vertex set X and edge set S. We compare algorithms by estimating the number of comparisons needed, as a function of n = |X|, and m = |S|.
In this paper, we review the information-theory lower bounds for the
set-maxima and local-sorting problems. We review deterministic
algorithms which have optimally solved the set-maxima problem, as a
function of m,n, in settings where extra assumptions about S have been
made. Also, we review randomized algorithms for local sorting and
set-maxima which achieve an optimal expected number of comparisons.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-05.ps.gz
DIMACS Home Page