From: schreiber@hpl.hp.com (Rob Schreiber) Subject: Pareto Sorting Date: 8 Mar 1999 14:29:48 -0500 Newsgroups: sci.math.num-analysis The problem of finding the Pareto-optimal points in a set of real d-tuples was addressed in a 1975 paper by H. T. Kung, F. Luccio, and F. P. Preparata (On finding the maxima of a set of vectors) which appeared in the Journal of the ACM. I asked Kung last year if there had been any further progress on this problem, and he knew of none. Their algorithm finds the Pareto optima in a set of n d-tuples in time O(n log n) for d = 2 and 3, and O(n log^{d-2} n) for d >= 4 (all logs are base 2.)