El problema de Weber y problemas de cubrimiento relacionados: polielipsoides.

Título: El problema de Weber y problemas de cubrimiento relacionados: polielipsoides.

Ponente: Víctor Blanco, Universdad de Granada

Organizador: Juan Aparicio

Fecha:  Lunes 27 de abril a las 12:00 horas.

Lugar:  Online (Se os facilitara aquí el link el mismo día 30 minutos antes de la charla para que podáis acceder)

meet.google.com/yvf-qbys-qcd

Resumen: En esta charla presentaré una extensión del problema clásico de encontrar el disco de menor tamaño cubriendo un conjunto dado de puntos en el plano, al caso de la búsqueda del polielipsoide de menor radio capaz de cubrir totalmente un conjunto de puntos en R^d. Este problema combina las dificultades propias del problema clásico de Weber y del problema conocido como el 1-centro contínuo. Veremos algunos resultados de complejidad sobre este, como la existencia de algoritmos polinomiales para el problema en caso en el que la dimensión y el número de focos del polielipsoide es fijo, y analizaré algunas formulaciones de programación matemática para el problema, que permiten conectar este problema con problemas clásicos de localización contínua, como el problema de Weber. Estudiaremos algunos algoritmos geométricos para resolver el problema en el caso en el que los focos son conocidos, así como el estudio no trivial del problema unidimensional. Presentaré además algunas extensiones del problema, como la búsqueda de los focos óptimos del polielipsoide a buscar, así como el uso de polielipsoides mediano-ordenados, a través de formulaciones como problemas de de programación no lineal entera mixta y estrategias más eficientes de resolución. Finalmente, mostraré algunos resultados computacionales que permiten analizar la dificultad empírica del problema y la eficiencia de los procedimientos propuestos.

.