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:
- 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.