1 Search Results for "Baweja, Anubhav"


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

Authors: Anubhav Baweja, Justin Jia, and David P. Woodruff

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


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.

Cite as

Anubhav Baweja, Justin Jia, and David P. Woodruff. An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.16},
  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}
}
  • Refine by Author
  • 1 Baweja, Anubhav
  • 1 Jia, Justin
  • 1 Woodruff, David P.

  • Refine by Classification
  • 1 Theory of computation → Sketching and sampling

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Minimum Feedback Arc Set
  • 1 Semi-streaming Algorithms
  • 1 Tournament Graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail