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

2018/06/06 by Dupin, Nicolas, Nielsen, Frank, Talbi, El-Ghazali
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1806.02098

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³) time and O(K.N) memory space when K\geqslant 3, cases K=2 having a time complexity in O(N²). 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.

Related

• Planar p-center problems are solvable in polynomial time when clustering a Pareto Front
• Exact Exponential Algorithms for Clustering Problems
• Center-based Clustering under Perturbation Stability
• Clustering under Perturbation Resilience
• Optimal interval clustering: Application to Bregman clustering and statistical mixture learning