Título: On the shortest path problem on hypergraphic polytopes
Día y lugar: Lunes 4/9 a las 14 hs. en la sala de reuniones 2119 del Pabellón 0+infinito. 
Orador: Mario Valencia-Pabon

Resumen:

For any submodular function f defined on the set [n], there is a convex polytope P_f which is called a polymatroid. From an optimization point of view, these are polytopes that generalize matroid base polytopes, while preserving the property that the vertices which are extremal with respect to a linear function can be found easily using a greedy algorithm. Hence, polymatroids yield a class of linear programs that are solvable in strongly polynomial time. 

One of the major combinatorial problem on n-dimensional polytopes is the one of finding a shortest path between two vertices of a graph formed by the vertices and edges of the polytope, where the length of the path is its number of edges. Bounding the length of such paths has been the topic of intensive research since the bird of the theory of linear programming and the invention by Dantzig of the Simplex algorithm. In this talk, I will survey some combinatorial and algorithmic results related to the shortest path problem on hypergraphic polytopes, a special families of polymatroids that have been studied extensively in the literature.

Aclaración: la charla será en español!

Son todos bienvenidos y si están interesados en participar frecuentemente en este seminario, los invitamos a unirse a nuestro grupo de Telegram: https://t.me/+RkVxwjjIdiE1Yjkx y visitar la página del seminario: https://web.dm.uba.ar/index.php/investigacion/seminarios/seminario-grafos 

Para quienes no puedan estar presencialmente, también está la oportunidad de participar virtualmente, pasaremos el link de Meet por el grupo de Telegram.