Algoritmos y combinatoria

Acerca del grupo de investigación

El grupo de Algoritmos y Combinatoria del Centro de Modelamiento Matemático se centra en el estudio de las propiedades estructurales de los grafos, el diseño y análisis de algoritmos centralizados y distribuidos, y el comportamiento de procesos en redes. Su investigación integra métodos de la teoría de grafos, la probabilidad y las ciencias de la computación teóricas para abordar preguntas fundamentales con relevancia tanto teórica como aplicada.

Un componente central del trabajo del grupo se encuentra en la combinatoria extremal y probabilística. Los temas de interés incluyen problemas de tipo Ramsey, Dirac y Turán en grafos aleatorios y deterministas, hipergrafos y grafos dirigidos. El grupo también trabaja en teoría de grafos estructural y algorítmica. Los temas de interés incluyen problemas de tipo Ramsey, contención de árboles y regularidad de grafos, así como direcciones más interdisciplinarias, como las propiedades geométricas que surgen de espacios métricos inducidos por grafos finitos y las conexiones entre la teoría de grafos y la teoría de grupos.

El grupo también desarrolla investigación sobre estructuras y procesos discretos aleatorios, así como algoritmos aleatorizados, con aplicaciones a la combinatoria y las ciencias de la computación. Esto incluye el estudio de modelos de redes complejas, procesos de difusión de información, grafos aleatorios y algoritmos de tiempo sublineal.

En computación distribuida, el grupo estudia sistemas compuestos por múltiples procesadores que cooperan para realizar tareas globales bajo restricciones intrínsecas, como el conocimiento limitado de la red y los recursos computacionales y de comunicación restringidos. La investigación en esta área se centra tanto en el diseño de algoritmos distribuidos eficientes como en el establecimiento de límites fundamentales mediante cotas inferiores y resultados de imposibilidad.

Finalmente, el grupo también realiza investigación en optimización combinatoria, con énfasis en enfoques exactos, de aproximación y poliédricos para problemas de optimización en grafos y matroides. También estudia algoritmos en línea y estocásticos para la optimización incremental bajo incertidumbre, incluyendo emparejamiento en línea, problemas de secretarias y emparejamiento estocástico.

Investigación fundamental

Investigadores

Coordinadores