Planar p-center problems are solvable in polynomial time when clustering a Pareto Front

Abstract

This paper is motivated by real-life applications of bi-objective optimization. Having many non dominated solutions, one wishes to cluster the Pareto front using Euclidian distances. The p-center problems, both in the discrete and continuous versions, are proven solvable in polynomial time with a common dynamic programming algorithm. Having $N$ points to partition in $K⩾3$ clusters, the complexity is proven in $O(KN\log N)$ (resp $O(KN{\log }^{2}N)$) time and $O(KN)$ memory space for the continuous (resp discrete) $K$-center problem. $2$-center problems have complexities in $O(N\log N)$. To speed-up the algorithm, parallelization issues are discussed. A posteriori, these results allow an application inside multi-objective heuristics to archive partial Pareto Fronts.