Seminario: “Diseño de algoritmos deterministas para problemas de optimización combinatoria”
21-OFecha: jueves 6 de enero de 2022 a las 11:00 hrs
Presenta: Dr. Joel Antonio Trejo Sánchez
Afiliación: CIMAT
Resumen:
La mayoría de los problemas de optimización combinatoria pertenecen a la clase de problemas NP-difícil. En esta charla se presentan un par de problemas de optimización combinatoria en gráficas. Se describe la dificultad de diseñar algoritmos, que en un tiempo razonable, nos aseguren obtener la solución óptima en estos problemas. Con el fin de solucionar dichos problemas, se presentan algunas relajaciones que permiten obtener la mejor solución en tiempo polinomial; es decir, en un tiempo razonable. Finalmente, se da un breve recorrido por los algoritmos de aproximación, los cuales permiten obtener una solución aproximada en una fracción del tiempo que requeriría obtener una solución óptima.
Semblanza:
Joel Antonio Trejo Sánchez obtuvo la licenciatura en ciencias de la computación en la Universidad Autónoma de Yucatán en 2003 y la maestría en Ingeniería con opción en Ciencias de la Computación por el Centro de Investigación y Estudios Avanzados del IPN en Guadalajara. Realizó el Doctorado en Ciencias de la Computación por el Centro de Investigación Científica y de Educación Superior de Ensenada en 2014. Su experiencia docente incluye cursos de licenciatura y posgrado en la Universidad del Caribe en Quintana Roo, la Universidad Autónoma de Yucatán y el Tecnológico Nacional de México en Mérida. Ha supervisado dos tesis de licenciatura y dos tesis de maestría. Su área de investigación incluye la teoría de la computación, los algoritmos distribuidos y los algoritmos paralelos. Su investigación ha sido financiada por el CONACYT en la convocatoria de Ciencias de Frontera. Es Miembro del Sistema Nacional de Investigadores desde el 2014.
Video del seminario: