Algorithms to identified nondominated solutions in a

multi-dimensional set


Luis Vicente Santana Quintero and Antonio López Jaimes implemented two different algorithms to identified the nondominated solutions from a data set.

  • The first algorithm has a complexity of O(n2) and actually is the most common used algorithm. The source code of this approach is available here (README).

 

  • The second algorithm was developed by Kung, Luccio and Preparata and finds the nondominated vectors (also called maximal elements) of a set of solutions. This algorithm requires O(n log n) comparisons for k = 2, and O(n (logk-2n)) comparisons for k >= 3, where n is the size of the input solution set and k is the dimension of the vectors. The source code of this approach is available here (README).

For details of the algorithm, refer to the following paper:

  1. H.T. Kung, F. Luccio, and F.P. Preparata. On finding the maxima of a set of vectors, Journal of the Association for Computing Machinery, 22(4):469-476, 1975

 

A data example to test both algorithms.