Unified Polynomial Dynamic Programming ...
Document type :
Compte-rendu et recension critique d'ouvrage
DOI :
Title :
Unified Polynomial Dynamic Programming Algorithms for P-Center Variants in a 2D Pareto Front
Author(s) :
Dupin, Nicolas [Auteur]
Laboratoire Interdisciplinaire des Sciences du Numérique [LISN]
Nielsen, Frank [Auteur]
Sony Computer Science Laboratories [Tokyo, Japan]
Talbi, El-Ghazali [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Laboratoire Interdisciplinaire des Sciences du Numérique [LISN]
Nielsen, Frank [Auteur]
Sony Computer Science Laboratories [Tokyo, Japan]
Talbi, El-Ghazali [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Journal title :
Mathematics
Pages :
453
Publisher :
MDPI
Publication date :
2021-02
ISSN :
2227-7390
English keyword(s) :
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
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
HAL domain(s) :
Informatique [cs]
Informatique [cs]/Complexité [cs.CC]
Computer Science [cs]/Operations Research [math.OC]
Mathématiques [math]/Optimisation et contrôle [math.OC]
Informatique [cs]/Géométrie algorithmique [cs.CG]
Informatique [cs]/Complexité [cs.CC]
Computer Science [cs]/Operations Research [math.OC]
Mathématiques [math]/Optimisation et contrôle [math.OC]
Informatique [cs]/Géométrie algorithmique [cs.CG]
English abstract : [en]
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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- Open access
- Access the document