2026-07-23T04:53:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15612 2024-03-06T10:55:45Z ddc:004 open_access

An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes Baweja, Anubhav Jia, Justin Woodruff, David P. Minimum Feedback Arc Set Tournament Graphs Approximation Algorithms Semi-streaming Algorithms We present the first semi-streaming polynomial-time approximation scheme (PTAS) for the minimum feedback arc set problem on directed tournaments in a small number of passes. Namely, we obtain a (1 + ε)-approximation in time O (poly(n) 2^{poly(1/ε)}), with p passes, in n^{1+1/p} ⋅ poly((log n)/ε) 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+ε)-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 largely unexplored territory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anubhav Baweja and Justin Jia and David P. Woodruff 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.16 urn:nbn:de:0030-drops-156128 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.16 eng https://creativecommons.org/licenses/by/4.0/legalcode