logo móvil
Contáctanos

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

Descargar PDF

Acceso abierto

Artículo científico


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Soluciones eficientes
Problema de optimización multiobjetivo
Frente de Pareto
Problemas -center
Variantes
Complejidades NP-hard

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 25

Citaciones: Sin citaciones


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.

Documentos Relacionados

Temas Virtualpro