Document Open Access Logo

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

Authors Anubhav Baweja, Justin Jia, David P. Woodruff

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.16.pdf
  • Filesize: 0.89 MB
  • 23 pages

Document Identifiers

Author Details

Anubhav Baweja
  • Carnegie Mellon University, Pittsburgh, PA, USA
Justin Jia
  • Carnegie Mellon University, Pittsburgh, PA, USA
David P. Woodruff
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Woodruff, David P.: partial support from NSF grant No. CCF-181584 and a Simons Investigator Award.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ITCS.2022.16

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sketching and sampling
Keywords
  • Minimum Feedback Arc Set
  • Tournament Graphs
  • Approximation Algorithms
  • Semi-streaming Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nir Ailon. An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity. The Journal of Machine Learning Research, 13(1):137-164, 2012. Google Scholar
  2. Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM), 55(5):1-27, 2008. Google Scholar
  3. Noga Alon. Ranking tournaments. SIAM Journal on Discrete Mathematics, 20(1):137-142, 2006. Google Scholar
  4. Sanjeev Arora, Alan Frieze, and Haim Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Mathematical programming, 92(1):1-36, 2002. Google Scholar
  5. Sepehr Assadi, Gillat Kol, Raghuvansh R Saxena, and Huacheng Yu. Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 354-364. IEEE, 2020. Google Scholar
  6. Sepehr Assadi and Ran Raz. Near-quadratic lower bounds for two-pass graph streaming algorithms. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 342-353. IEEE, 2020. Google Scholar
  7. Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, and Ron M Roth. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference. SIAM journal on computing, 27(4):942-959, 1998. Google Scholar
  8. Shuvra S Bhattacharyya, Praveen K Murthy, and Edward A Lee. Synthesis of embedded software from synchronous dataflow specifications. Journal of VLSI signal processing systems for signal, image and video technology, 21(2):151-166, 1999. Google Scholar
  9. Glencora Borradaile, Claire Mathieu, and Theresa Migler. Lower bounds for testing digraph connectivity with one-pass streaming algorithms. CoRR, abs/1404.1323, 2014. URL: http://arxiv.org/abs/1404.1323.
  10. Felix Brandt, Markus Brill, and Bernhard Harrenstein. Tournament solutions, 2016. Google Scholar
  11. Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova. Vertex ordering problems in directed graph streams, 2019. Google Scholar
  12. Pierre Charbit, Stéphan Thomassé, and Anders Yeo. The minimum feedback arc set problem is np-hard for tournaments. Combinatorics, Probability and Computing, 16:01-04, 2007. Google Scholar
  13. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, and Huacheng Yu. Almost optimal super-constant-pass streaming lower bounds for reachability. Electron. Colloquium Comput. Complex., 28:27, 2021. URL: https://eccc.weizmann.ac.il/report/2021/027.
  14. William W Cohen, Robert E Schapire, and Yoram Singer. Learning to order things. In Advances in neural information processing systems, pages 451-457, 1998. Google Scholar
  15. Don Coppersmith, Lisa Fleischer, and Atri Rudra. Ordering by weighted number of wins gives a good ranking for weighted tournaments. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 776-782, 2006. Google Scholar
  16. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2-3):207-216, 2005. Google Scholar
  17. Paola Festa, Panos M Pardalos, and Mauricio GC Resende. Feedback set problems. In Handbook of combinatorial optimization, pages 209-258. Springer, 1999. Google Scholar
  18. Alan Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combinatorica, 19(2):175-220, 1999. Google Scholar
  19. Xiubo Geng, Tie-Yan Liu, Tao Qin, Andrew Arnold, Hang Li, and Heung-Yeung Shum. Query dependent ranking using k-nearest neighbor. In Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, pages 115-122, 2008. Google Scholar
  20. Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. Algorithmica, 76(3):654-683, 2016. Google Scholar
  21. Daniel M Kane, Jelani Nelson, and David P Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1161-1178. SIAM, 2010. Google Scholar
  22. Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 95-103, 2007. Google Scholar
  23. Luigi Laura and Federico Santaroni. Computing strongly connected components in the streaming model. In International Conference on Theory and Practice of Algorithms in (Computer) Systems, pages 193-205. Springer, 2011. Google Scholar
  24. Andrew McGregor. Graph stream algorithms: a survey. ACM SIGMOD Record, 43(1):9-20, 2014. Google Scholar
  25. Antti-Veikko Rosti, Necip Fazil Ayan, Bing Xiang, Spyros Matsoukas, Richard Schwartz, and Bonnie Dorr. Combining outputs from multiple machine translation systems. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 228-235, 2007. Google Scholar
  26. Aiguo Xie and Peter A Beerel. Implicit enumeration of strongly connected components and an application to formal verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19(10):1225-1230, 2000. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact