An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes

Anubhav Baweja, Justin Jia, David P. Woodruff

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+\epsilon )$-appro…