Unified Polynomial Dynamic Programming Algorithms for P-Center Variants in a 2D Pareto Front

Nicolas Dupin, Frank Nielsen and El-Ghazali Talbi
Additional contact information
Nicolas Dupin: Université Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Numérique, 91400 Orsay, France
Frank Nielsen: Sony Computer Science Laboratories Inc., Tokyo 141-0022, Japan
El-Ghazali Talbi: CNRS UMR 9189-CRIStAL-Centre de Recherche en Informatique Signal et Automatique de Lille, Université Lille, F-59000 Lille, France

Mathematics, 2021, vol. 9, issue 4, 1-30

Abstract: 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 ) N 2 ) 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.

Keywords: discrete optimization; operational research; computational geometry; complexity; algorithms; dynamic programming; clustering; k-center; p-center; sum-radii clustering; sum-diameter clustering; bi-objective optimization; Pareto Front; parallel programming (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/4/453/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/4/453/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:4:p:453-:d:504614

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().