Sumas de Pareto de conjuntos de Pareto: límites inferiores y algoritmos

Área de la Ciencia:

• Algoritmos de optimización
• Geometría computacional
• Investigación de las operaciones

Sus antecedentes:

• Los problemas de optimización de bicriterios requieren el cálculo de soluciones óptimas de Pareto.
• Los algoritmos existentes a menudo implican conjuntos de soluciones de fusión y filtrado.
• El cálculo eficiente de la suma de Pareto de dos conjuntos de Pareto es un desafío clave.

Objetivo del estudio:

• Desarrollar nuevos algoritmos para calcular la suma de Pareto de dos conjuntos de Pareto.
• Para lograr un cálculo eficiente sin formar explícitamente la suma completa de Minkowski.
• Analizar el rendimiento teórico y la aplicabilidad práctica de nuevos algoritmos.

Principales métodos:

• Desarrollo de algoritmos sucesivos sensibles a la salida para el cálculo de la suma de Pareto.
• Análisis de la complejidad temporal y espacial, incluidos los límites inferiores condicionales.
• Técnicas de ingeniería para la mejora práctica del rendimiento y la validación experimental.

Principales resultados:

• Un algoritmo sucesivo sensible a la salida con O ((n log n + nk) tiempo de ejecución y O ((n + k) espacio.
• Se demuestra un límite inferior condicional para el cálculo de la suma de Pareto.
• Los algoritmos demuestran un rendimiento mejorado, especialmente para grandes sumas de Pareto, y una eficiencia práctica.

Conclusiones:

• Los nuevos algoritmos proporcionan mejoras significativas en la eficiencia del cálculo de la suma de Pareto.
• Los métodos desarrollados son eficaces para abordar instancias más grandes en aplicaciones como la planificación de rutas.
• El consumo de espacio sensible a la salida es clave para manejar problemas de optimización complejos.