## DIMACS TR: 98-05

## The Set-Maxima Problem, an Overview

### Author: Richard Desper

**
ABSTRACT
**

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