English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present the first semi-streaming PTAS for the minimum feedback arc setproblem on directed tournaments in a small number of passes. Namely, we obtaina $(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 previousalgorithm 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 linearnumber of passes. We also present a new time/space trade-off for $1$-passalgorithms that solve the tournament feedback arc set problem. This problem hasseveral applications in machine learning such as creating linear classifiersand doing Bayesian inference. We also provide several additional algorithms andlower bounds for related streaming problems on directed graphs, which is amostly unexplored territory.

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