  We present the first semi-streaming PTAS for the minimum feedback arc set
problem on directed tournaments in a small number of passes. Namely, we obtain
a $(1 + \varepsilon)$-approximation in polynomial time $O \left( \text{poly}(n)
2^{\text{poly}(1/\varepsilon)} \right)$, with $p$ passes in $n^{1+1/p} \cdot
\text{poly}\left(\frac{\log n}{\varepsilon}\right)$ space. The only previous
algorithm with this pass/space trade-off gave a $3$-approximation (SODA, 2020),
and other polynomial-time algorithms which achieved a
$(1+\varepsilon)$-approximation did so with quadratic memory or with a linear
number of passes. We also present a new time/space trade-off for $1$-pass
algorithms that solve the tournament feedback arc set problem. This problem has
several applications in machine learning such as creating linear classifiers
and doing Bayesian inference. We also provide several additional algorithms and
lower bounds for related streaming problems on directed graphs, which is a
mostly unexplored territory.
