An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes
summary
Claims a one plus epsilon PTAS for tournament Feedback Arc Set running in semi‑streaming memory using sampling and local moves. Algorithm approximates single‑vertex move gains with Ostar(n) stored samples, executes strong single vertex moves in parallel via an ApproxLocalImprove routine, and recurses like randomized Quicksort on pivots. Uses Ostar(n) space with O(log n) passes (tradeoff to Ostar(n^{1+1/p}) space in p passes), and handles small subproblems by brute force or additive approximations.
AI-written summary · about