Wednesday, February 10 at 3:00pm to 4:00pm
Patricia Hersh, University of Oregon
Abstract: Given a polytope P and a nonzero vector c, the question of which point in P has largest inner product (or smallest inner product) with c is the main goal of linear programming in operations research. Key to efficiency questions regarding linear programming is the directed graph G(P,c) on the 1-skeleton of P obtained by directing each edge e(u,v) from u to v for c(u) < c(v) and in particular the diameter of G(P,c). We will explore the question of finding sufficient conditions on P and c to guarantee that no directed path ever revisits any polytope face that it has left; this is enough to ensure that linear programming is efficient under all possible choices of pivot rule. It turns out that poset-theoretic techniques and poset topology can help shed light on this question. In discussing work on this question, we will provide background along the way.
Please see your email to join via zoom