Encontrar una solución que maximiza (o minimiza) un conjunto de restricciones lineales se conoce como programación lineal. Uno de los algoritmos más conocidos para resolver este problema es el simplex. Cuando la dimensión del problema (el número de variables) es relativamente pequeña, algunos algoritmos geométricos pueden comportarse de manera más eficiente que este método.
En esta charla veremos qué es un problema de tipo LP, cómo podemos resolverlo eficientemente con el algoritmo recursivo de Matousek, Sharir y Welzl, y cómo se puede calcular su eficiencia con el análisis "hacia atrás" (backwards analysis). A continuación, veremos un ejemplo de problema LP: el cálculo del menor círculo contenedor. Se verá cómo se adapta el algoritmo general al problema concreto en dos dimensiones y cómo construir una solución iterativa. Por último, se generalizará el algoritmo iterativo a d dimensiones.
Fecha: 27 de mayo
Lugar: Aula 6306 (Bloque 6) Facultad de Informática, Univ. Politécnica Madrid
Dirección: Campus de Montegancedo, 28660-Boadilla del Monte, Madrid
