Conferencia del prof. Dr. Francisco Santos Leal

Título: Programación lineal, método del símplice, y conjetura de Hirsch
Ponente: Francisco Santos Leal
Fecha: 15/03/2016 13:00 h
Lugar: Sala de Seminarios, Edificio Torretamarit
Resumen:
Aunque se conocen algoritmos polinómicos para la programación lineal, todos son «de aproximaciones sucesivas” y dependen por tanto del tamaño bit de los coeficientes del input. En particular, no son “fuertemente polinómicos”. En cambio, el método más utilizado (el método símplex) que se basa en la combinatoria de politopos y no en aproximaciones, no se sabe si es polinómico o no, a pesar de que en la práctica es igual o mejor que los otros. Una de las razones para nuestra ignorancia es que no sabemos cómo de grande puede ser el diámetro combinatorio de un politopo (es decir, un poliedro de dimensión superior) en función de su dimensión y del número de desigualdades lineales necesarias para definirlo. Esta es la llamada Conjetura de Hirsch, que en su versión original afirmaba que dicho diámetro no puede exceder de «número de desigualdades menos dimensión». Aunque la conjetura fue refutada en el caso no acotado por Klee y Walkup (1967) y en el caso acotado por el autor (2012), los contraejemplos conocidos no dicen mucho sobre la pregunta subyacente: no conocemos ningún politopo de diámetro mayor que 1.05 veces la conjetura de Hirsch, y tampoco somos capaces de demostrar ninguna cota superior polinómica para dicho diámetro. Esta pregunta, la existencia de cotas polinómicas para el diámetro de politopos, ha sido habitualmente atacada mediante su generalización a objetos más abstractos que los politopos, típicamente complejos simpliciales con alguna propiedad adicional. En esta charla explicaremos las relaciones entre el método símplex y la Conjetura de Hirsch y describiremos la situación actual del problema y algunas aproximaciones abstractas al mismo.
Breve Bio:
Francisco Santos Leal (Valladolid, 1968) es catedrático de Geometría y Topología de la Universidad de Cantabria. Ha recibido el Premio Joven de Ciencia y Tecnología de la Fundación Complutense (2003) y el Premio Humboldt de Investigación (2013) en reconocimiento a su labor científica. Fue conferenciante invitado en la sección de Combinatoria del XXV Congreso Internacional de Matemáticos (Madrid, 2006). El profesor Santos trabaja Geometría Discreta y Computacional, especialmente en aspectos combinatorios y geométricos de teoría de politopos. Uno de sus logros más notables fue la refutación de la conjetura de Hirsch (planteada en 1957). En la base de datos MathSciNet constan 75 publicaciones con 594 citas por 467 autores.