Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Unified Polynomial Dynamic Programming Algorithms for P-Center Variants in a 2D Pareto Front
Ist Teil von
Mathematics (Basel), 2021-02, Vol.9 (4), p.453
Ort / Verlag
Basel: MDPI AG
Erscheinungsjahr
2021
Quelle
Electronic Journals Library
Beschreibungen/Notizen
With many efficient solutions for a multi-objective optimization problem, this paper aims to cluster the Pareto Front in a given number of clusters K and to detect isolated points. K-center problems and variants are investigated with a unified formulation considering the discrete and continuous versions, partial K-center problems, and their min-sum-K-radii variants. In dimension three (or upper), this induces NP-hard complexities. In the planar case, common optimality property is proven: non-nested optimal solutions exist. This induces a common dynamic programming algorithm running in polynomial time. Specific improvements hold for some variants, such as K-center problems and min-sum K-radii on a line. When applied to N points and allowing to uncover M<N points, K-center and min-sum-K-radii variants are, respectively, solvable in O(K(M+1)NlogN) and O(K(M+1)N2) time. Such complexity of results allows an efficient straightforward implementation. Parallel implementations can also be designed for a practical speed-up. Their application inside multi-objective heuristics is discussed to archive partial Pareto fronts, with a special interest in partial clustering variants.