Speaker: Deeparnab Chakrabarty Title: Steiner Trees - Geometry, Linear Programs and Algorithms Abstract: In this talk, we investigate the bidirected cut LP relaxation for the Minimum Steiner Tree problem. We use geometry to devise a new lower bound on the cost of any Steiner tree. The lower bound is captured via an LP which we call the simplex-embedding LP. A short description of it is that it is an l_1-embedding of the graph on a simplex, maximizing a certain linear objective function. Interestingly, the dual of the LP turns out to be equivalent to the bi-directed cut relaxation. For quasi-bipartite graphs, graphs which have no Steiner-Steiner edges, we will show how we improve the upper bound on the integrality gap of our LP relaxation (and hence as well as the bidirected cut LP relaxation). In this talk, we will show an upper bound of $\sqrt{2}$ which improves upon the known 3/2. We will also indicate how this can be further improved to 4/3. In contrast, the best lower bound known is 8/7 by Martin Skutella. This is joint work with Nikhil R. Devanur and Vijay V. Vazirani.