DIMACS TR: 98-05

The Set-Maxima Problem, an Overview

Author: Richard Desper


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