Título: On the shortest path problem on hypergraphic polytopes
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.