k-medoids and p-median clustering are solvable in polynomial time for a 2d Pareto front

Nicolas Dupin, Frank Nielsen, El-Ghazali Talbi

Abstract

This paper examines a common extension of k-medoids and k-median clustering in the case of a two-dimensional Pareto front, as generated by bi-objective optimization approaches. A characterization of optimal clusters is provided, which allows to solve the optimization problems to optimality in polynomial time using a common dynamic programming algorithm. More precisely, having $N$ points to cluster in $K$ subsets, the complexity of the algorithm is proven in $O(N^3)$ time and $O(K.N)$ memory space when $K\geqslant 3$, cases $K=2$ having a time complexity in $O(N^2)$. Furthermore, speeding-up the dynamic programming algorithm is possible avoiding useless computations, for a practical speed-up without improving the complexity. Parallelization issues are also discussed, to speed-up the algorithm in practice.
BibTeX
@misc{dupin2018k,
  author = {Nicolas Dupin and Frank Nielsen and El-Ghazali Talbi},
  title = {{k-medoids and p-median clustering are solvable in polynomial time for a 2d Pareto front}},
  year = {2018},
  eprint = {1806.02098},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.02098},
}

Loading related content...

Figure