Algoritmos dinámicos unificados de programación polinómica para variantes del P-Center en un frente de Pareto 2D
Autores: Dupin, Nicolas; Nielsen, Frank; Talbi, El-Ghazali
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
Categoría
Matemáticas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 20
Citaciones: Sin citaciones
Con muchas soluciones eficientes para un problema de optimización multiobjetivo, este documento tiene como objetivo agrupar el Frente de Pareto en un número dado de clústeres y detectar puntos aislados. Se investigan problemas de -centro y sus variantes con una formulación unificada considerando las versiones discretas y continuas, problemas parciales de -centro y sus variantes de radios mínimos. En tres dimensiones (o más), esto induce complejidades NP-duros. En el caso plano, se demuestra una propiedad de optimalidad común: existen soluciones óptimas no anidadas. Esto induce un algoritmo común de programación dinámica que se ejecuta en tiempo polinómico. Se mantienen mejoras específicas para algunas variantes, como problemas de -centro y radios de suma mínima en una línea. Cuando se aplican a N puntos y se permite descubrir puntos, las variantes de K-centro y radios de suma mínima son, respectivamente, solucionables en y tiempo. Esta complejidad de resultados permite una implementación directa eficiente. También se pueden diseñar implementaciones paralelas para una aceleración práctica. Se discute su aplicación dentro de heurísticas multiobjetivo para archivar frentes de Pareto parciales, con un interés especial en las variantes de agrupamiento parcial.
Descripción
Con muchas soluciones eficientes para un problema de optimización multiobjetivo, este documento tiene como objetivo agrupar el Frente de Pareto en un número dado de clústeres y detectar puntos aislados. Se investigan problemas de -centro y sus variantes con una formulación unificada considerando las versiones discretas y continuas, problemas parciales de -centro y sus variantes de radios mínimos. En tres dimensiones (o más), esto induce complejidades NP-duros. En el caso plano, se demuestra una propiedad de optimalidad común: existen soluciones óptimas no anidadas. Esto induce un algoritmo común de programación dinámica que se ejecuta en tiempo polinómico. Se mantienen mejoras específicas para algunas variantes, como problemas de -centro y radios de suma mínima en una línea. Cuando se aplican a N puntos y se permite descubrir puntos, las variantes de K-centro y radios de suma mínima son, respectivamente, solucionables en y tiempo. Esta complejidad de resultados permite una implementación directa eficiente. También se pueden diseñar implementaciones paralelas para una aceleración práctica. Se discute su aplicación dentro de heurísticas multiobjetivo para archivar frentes de Pareto parciales, con un interés especial en las variantes de agrupamiento parcial.