Session:

LBP - Late Breaking Papers

Title:

KLP Not Always Efficient

Authors:

Sanyou Zeng
Lixin Ding
Shuzhen Yao
Lishan Kang

Abstract:

The size of the nondominated set of a vector set is greatly dependent on the size of the original vector set $N$ and the dimension of the vector $M$. Theoretical analysis shows that when $M=O(\log N)$ the original set has big nondominated set which may be the original set itself, and in the case $M=O(\log N)$, a classical algorithm (KLP) for finding nondominated set has complexity of KLP higher than $N^2$. Experiment verifies the analysis result as well. Therefore, we should avoid employing KLP when $M=O(\log N)$.