Skip to content

Algorithms: Set Intersection Sort

Maxim Buzdalov edited this page Dec 13, 2019 · 1 revision
@online{ merge-nds,
    author = {Javier Moreno and Daniel Rodriguez and
              Antonio Jesús Nebro and Jose Lozano},
    title = {Merge Non-Dominated Sorting Algorithm
             for Many-Objective Optimization},
    url = {https://arxiv.org/abs/1809.06106}
}

This algorithm is called "Merge Non-Dominated Sorting" for a heavy use of sorting. As it is a bad idea to name the algorithm after a particular O(N log N) algorithm for sorting, in my implementation I call it the "Set Intersection Sort", since it describes the idea better: for any given point, it eventually intersects the sets of points that can, in principle, dominate that point based on how the points are ordered according to every objective, in order.

How to get an instance:

  • SetIntersectionSort.getBitSetInstance() -- returns a bitset-based implementation of the set intersection sort. The memory requirement is O(N^2), and the performance is very impressive for large dimensions (seems to be the fastest for M>10 as of now).
Clone this wiki locally