Algorithms: Jensen‐Fortin‐Buzdalov divide‐and‐conquer

@article{ jensen,
    author      = {Mikkel T. Jensen},
    title       = {Reducing the Run-time Complexity of Multiobjective {EA}s:
                   The {NSGA}-{II} and Other Algorithms},
    journal     = {IEEE Transactions on Evolutionary Computation},
    volume      = {7},
    number      = {5},
    year        = {2003},
    pages       = {503-515},
    publisher   = {IEEE Press},
    langid      = {english}
}

@inproceedings{ fortin,
    author      = {Fortin, F{\'e}lix-Antoine and Grenier, Simon and Parizeau, Marc},
    title       = {Generalizing the Improved Run-time Complexity Algorithm
                   for Non-dominated Sorting},
    booktitle   = {Proceedings of Genetic and Evolutionary Computation Conference},
    year        = {2013},
    pages       = {615-622},
    publisher   = {ACM},
    langid      = {english}
}

@incollection{ buzdalov,
    author      = {Maxim Buzdalov and Anatoly Shalyto},
    title       = {A Provably Asymptotically Fast Version of the Generalized
                   Jensen Algorithm for Non-Dominated Sorting},
    booktitle   = {Parallel Problem Solving from Nature -- {PPSN} {XIII}},
    series      = {Lecture Notes in Computer Science},
    number      = {8672},
    year        = {2014},
    pages       = {528-537},
    publisher   = {Springer},
    langid      = {english}
}

@incollection{ markinaB-ppsn18-nds-hybrid,
    author     = {Margarita Markina and Maxim Buzdalov},
    title      = {Towards Large-Scale Multiobjective Optimisation
                  with a Hybrid Algorithm for Non-Dominated Sorting},
    booktitle  = {Parallel Problem Solving from Nature -- PPSN XV},
    volume     = {1},
    year       = {2018},
    pages      = {347-358},
    series     = {Lecture Notes in Computer Science},
    number     = {11101},
    langid     = {english}
}

@incollection{ buzdalov-emo19-veb-nds,
    author     = {Maxim Buzdalov},
    title      = {Make Evolutionary Multiobjective Algorithms Scale Better 
                  with Advanced Data Structures:
                  Van Emde Boas Tree for Non-Dominated Sorting},
    booktitle  = {Proceedings of International Conference on
                  Evolutionary Multi-Criterion Optimization},
    series     = {Lecture Notes in Computer Science},
    number     = {11411},
    year       = {2019},
    pages      = {66-77},
    langid     = {english}
}

Many implementations of this algorithm available in this project (except for the implementations based on the van Emde Boas tree) support using multiple threads to improve performance. The argument int threads controls precisely this. Any number greater than 1 for this argument creates an instance with a ForkJoinPool using this number of threads. A single-threaded version can be created with threads = 1. When threads <= 0, all available threads are used if necessary.

Speed-ups from using multiple threads are heavily data-dependent. The general rule is as follows: better speed-ups come with greater dimensions and larger number of points. In particular, M = 2 and M = 3 are unaffected by multiple threads (they are fast anyway). The maximum possible speed-up, seen in experiments, seems to be around half the number of threads plus something.

How to get an instance:

• JensenFortinBuzdalov.getRedBlackTreeSweepImplementation(int threads) -- returns an implementation of the principles from all three works, which uses red-black trees in sweep-line subroutines. The memory complexity is O(MN), the worst-case running time complexity is O(min(MN^2, N (log N)^(M - 1))).
• JensenFortinBuzdalov.getFenwickSweepImplementation(int threads) -- same as above, but with Fenwick tree for sweep-lines. This is always slower than the previous one.
• JensenFortinBuzdalov.getRedBlackTreeSweepHybridFNDSImplementation(int threads) -- returns a hybrid implementation, which works as the red-black tree implementation, but switches to linear-memory fast non-dominated sorting on small enough subproblems. This version works much faster than the simple red-black-tree implementation at M>2. The memory requirements are O(MN), and no meaningful upper bounds are known other than O(min(MN^2, N (log N)^(M - 1))).
• JensenFortinBuzdalov.getRedBlackTreeSweepHybridENSImplementation(int threads) -- returns a hybrid implementation, based on the same idea as the one above, but using a customized ENS algorithm.
• JensenFortinBuzdalov.getRedBlackTreeSweepHybridNDTImplementation(int threshold, int threads) -- returns a hybrid implementation, based on the same idea as the one above, but using a customized ENS-NDT algorithm. The threshold parameter corresponds to the ENS-NDT threshold parameter (see Non-Dominated Tree for explanation), and its optimal value is somewhere between 2 and 8.
• JensenFortinBuzdalov.getVanEmdeBoasImplementation -- returns an implementation which uses a sorted set based on the van Emde Boas tree for solving two-dimensional subproblems. Its runtime worst-case upper bound is O(min(MN^2, N (log N)^(M - 2) log log N)), that is, it is asymptotically faster than all other existing implementations. Currently it does not support multiple threads.
• JensenFortinBuzdalov.getVanEmdeBoasHybridENSImplementation -- returns an implementation which uses the same van Emde Boas tree and a customized ENS algorithm for solving small subproblems. As for the previous one, its runtime worst-case upper bound is O(min(MN^2, N (log N)^(M - 2) log log N)). It is faster than the red-black tree implementation on multiple-front datasets, and not slower on single-front ones. Currently it does not support multiple threads.
• JensenFortinBuzdalov.getVanEmdeBoasHybridNDTImplementation(int threshold) -- returns an implementation which uses the van Emde Boas tree and a customized ENS-NDT algorithm for solving small subproblems. Currently it does not support multiple threads.