In the Directed Steiner Tree problem, we are given a directed graph G = (V,E) with edge costs, a root vertex r ∈ V, and a terminal set X ⊆ V . The goal is to find the cheapest subset of edges that contains an r-t path for every terminal t ∈ X. The only known polylogarithmic approximations for Directed Steiner Tree run in quasi-polynomial time and the best polynomial time approximations only achieve a guarantee of O(|X|^ε) for any constant ε > 0. Furthermore, the integrality gap of a natural LP relaxation can be as bad as Ω(√|X|).  We demonstrate that l rounds of the Sherali-Adams hierarchy suffice to reduce the integrality gap of a natural LP relaxation for Directed Steiner Tree in l-layered graphs from Ω( k) to O(l · log k) where k is the number of terminals. This is an improvement over Rothvoss’ result that 2l rounds of the considerably stronger Lasserre SDP hierarchy reduce the integrality gap of a similar formulation to O(l · log k). We also observe that Directed Steiner Tree instances with 3 layers of edges have only an O(logk) integrality gap bound in the standard LP relaxation, complementing the fact that the gap can be as large as Ω(√k) in graphs with 4 layers. Finally, we consider quasi-bipartite instances of Directed Steiner Tree meaning no edge in E connects two Steiner nodes V − (X ∪ {r}). By a simple reduction from Set Cover, it is still NP-hard to approximate quasi-bipartite instances within a ratio better than O(log|X|). We present a polynomial-time O(log |X|)-approximation for quasi-bipartite instances of Directed Steiner Tree. Our approach also bounds the integrality gap of the natural LP relaxation by the same quantity. A novel feature of our algorithm is that it is based on the primal-dual framework, which typically does not result in good approximations for network design problems in directed graphs.

Probabilistic graphical modeling is a framework which can be used to succinctly<br>represent multivariate probability distributions of time series in terms of each time<br>series’s dependence on others. In general, it is computationally prohibitive to sta-<br>tistically infer an arbitrary model from data. However, if we constrain the model to<br>have a tree topology, the corresponding learning algorithms become tractable. The<br>expressive power of tree-structured distributions are low, since only n − 1 dependen-<br>cies are explicitly encoded for an n node tree. One way to improve the expressive<br>power of tree models is to combine many of them in a mixture model. This work<br>presents and uses simulations to validate extensions of the standard mixtures of trees<br>model for i.i.d data to the setting of time series data. We also consider the setting<br>where the tree mixture itself forms a hidden Markov chain, which could be better<br>suited for approximating time-varying seasonal data in the real world. Both of these<br>are evaluated on artificial data sets.<br><br>