Fecha: jueves 5 de junio de 2025
Hora: 16:15hrs.
Lugar: B05 (Beauchef 851, piso -1)
Abstract: La optimización en línea es una herramienta fundamental en la toma de decisiones, con aplicaciones que van desde la asignación de recursos en tiempo real hasta la selección de personal y los mercados de subastas. En esta charla se presentarán los dos problemas emblemáticos del área: el Problema del Secretario y las Desigualdades de Profeta. A través de un recorrido histórico, se mostrará cómo ambos problemas surgieron como modelos teóricos para capturar la incertidumbre y la secuencialidad en la toma de decisiones. Repasaremos algoritmos clásicos e introduciremos una relajación del Problema del Secretario en Matroides que definimos Multiple Matroid Secretary Problem justo con los resultados obtenidos. En particular, presentaremos el mejor algoritmo para J-MSP en la clase de matroide transversales y demostramos su optimalidad. Finalmente, mostraremos parte de la investigación en curso sobre el 1-out-of-k Prophet Inequality, explorando nuevas cotas de aproximación que reduzcan la brecha entre el óptimo en línea y el óptimo con información completa.