Skip to content
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Publication Details
AFRICAN RESEARCH NEXUS
SHINING A SPOTLIGHT ON AFRICAN RESEARCH
Unified polynomial dynamic programming algorithms for p-center variants in a 2d pareto front
Mathematics, Volume 9, No. 4, Article 453, Year 2021
Notification
URL copied to clipboard!
Description
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)N log N) 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. © 2021 by the authors. Licensee MDPI, Basel, Switzerland.
Authors & Co-Authors
Talbi, Emna Ghazali
France, Paris
Cnrs Centre National de la Recherche Scientifique
Statistics
Citations: 10
Authors: 1
Affiliations: 2
Identifiers
Doi:
10.3390/math9040453
ISSN:
22277390