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 @math points to partition in @math clusters, the complexity is proven in @math (resp @math ) time and @math memory space for the continuous (resp discrete) @math -center problem. @math -center problems have complexities in @math . 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.
We note that an affine 2d PF is a line in @math , clustering is equivalent to 1 dimensional cases. 1-dimension K-means was proven to be solvable in polynomial time with a DP algorithm in @math time and @math space. This complexity was improved for a DP algorithm in @math time and @math space in @cite_5 . This is thus the complexity of K-means in an affine 2d PF. The specific case, already mentioned in the previous section, of the continuous p-center problem with centers on a straight line is more general that the case of an affine 2d PF, with a complexity proven in @math time and @math space by @cite_34 . 2d cases of clustering problems can also be seen as specific cases of three-dimensional (3d) PF, affine 3d PF. Having NP-hard complexities proven for planar cases of clustering, which is the case for k-means, p-median, k-medoids, p-center problems since @cite_44 @cite_1 , it implies that the considered clustering problems are also NP-hard for 3d PF.
@cite_44 @cite_5 @cite_34 @cite_1
2582351091 2755780781 2032624334
The @math -Means clustering problem on @math points is NP-Hard for any dimension @math , however, for the 1D case there exists exact polynomial time algorithms. Previous literature reported an @math time dynamic programming algorithm that uses @math space. It turns out that the problem has been considered under a different name more than twenty years ago. We present all the existing work that had been overlooked and compare the various solutions theoretically. Moreover, we show how to reduce the space usage for some of them, as well as generalize them to data structures that can quickly report an optimal @math -Means clustering for any @math . Finally we also generalize all the algorithms to work for the absolute distance and to work for any Bregman Divergence. We complement our theoretical contributions by experiments that compare the practical performance of the various algorithms. Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows: An @math algorithm for the continuous p-center problem on a tree is presented. Following a sequence of previous algorithms, ours is the first one whose time bound in uniform in p and less than quadratic in n. We also present an @math algorithm for a weighted discrete p-center problem.