License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.16
URN: urn:nbn:de:0030-drops-156128
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15612/
Go to the corresponding LIPIcs Volume Portal

Baweja, Anubhav ; Jia, Justin ; Woodruff, David P.

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

pdf-format:
LIPIcs-ITCS-2022-16.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{baweja_et_al:LIPIcs.ITCS.2022.16,
  author =	{Baweja, Anubhav and Jia, Justin and Woodruff, David P.},
  title =	{{An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15612},
  URN =		{urn:nbn:de:0030-drops-156128},
  doi =		{10.4230/LIPIcs.ITCS.2022.16},
  annote =	{Keywords: Minimum Feedback Arc Set, Tournament Graphs, Approximation Algorithms, Semi-streaming Algorithms}
}

Keywords: Minimum Feedback Arc Set, Tournament Graphs, Approximation Algorithms, Semi-streaming Algorithms
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI