Clustering in a 2-dimensional Pareto Front: the p-median and p-center problems are polynomially solvable
share
This paper is motivated by a real life application of multi-objective optimization without preference. Having many non-dominated solutions with Pareto dominance, the problem is to select and present a small number of representative solutions to decision makers. The p-median and p-center clustering problems are investigated in this paper for the 2-dimensional case assuming that the points to cluster are not comparable in R^2. This paper proves that these clustering problems can be solved to optimality with a unified dynamic programming algorithm. Having N points to partition in K clusters, a polynomial complexity is proven in O(N^3) for the p-median problem, in O(N^2.(K + N)) for the discrete p-center problem and in O(K.N^2) for the continuous p-center problem. The dynamic programming algorithm can be adapted to consider cardinality constraints for the clusters, which can improve the complexities. These algorithms allows furthermore a natural parallel implementation. A posteriori, the complexity of the clustering algorithms allows also to consider these algorithms inside multi-objective meta-heuristics to archive diversified non-dominated points along the Pareto front.
READ FULL TEXT