 |
    |
A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting
Maxim Buzdalov and Anatoly Shalyto
ITMO University 49 Kronverkskiy prosp. 197101, Saint-Petersburg, Russiabuzdalov@rain.ifmo.ru
shalyto@mail.ifmo.ru
Abstract. The non-dominated sorting algorithm by Jensen, generalized by Fortin et al to handle the cases of equal objective values, has the running time complexity of O(N logK – 1 N) in the general case. Here N is the number of points, K is the number of objectives and K is thought to be a constant when N varies. However, the complexity was not proven to be the same in the worst case.
A slightly modified version of the algorithm is presented, for which it is proven that its worst-case running time complexity is O(N logK – 1 N).
Keywords: Non-dominated sorting, worst-case running time complexity, multi-objective optimization
LNCS 8672, p. 528 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014