Document Open Access Logo

Sublinear Algorithms for MAXCUT and Correlation Clustering

Authors Aditya Bhaskara, Samira Daruki, Suresh Venkatasubramanian

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.16.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Aditya Bhaskara
  • School of Computing, University of Utah, USA, http://www.cs.utah.edu/~bhaskara
Samira Daruki
  • Expedia Research, USA, https://sites.google.com/site/samiradaruki
Suresh Venkatasubramanian
  • School of Computing, University of Utah, USA, http://www.cs.utah.edu/~suresh

Funding

This research was supported in part by National Science Foundation under grants IIS-1251049, IIS-1633724

Cite As Get BibTex

Aditya Bhaskara, Samira Daruki, and Suresh Venkatasubramanian. Sublinear Algorithms for MAXCUT and Correlation Clustering. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.16

Abstract

We study sublinear algorithms for two fundamental graph problems, MAXCUT and correlation clustering. Our focus is on constructing core-sets as well as developing streaming algorithms for these problems. Constant space algorithms are known for dense graphs for these problems, while Omega(n) lower bounds exist (in the streaming setting) for sparse graphs.
Our goal in this paper is to bridge the gap between these extremes. Our first result is to construct core-sets of size O~(n^{1-delta}) for both the problems, on graphs with average degree n^{delta} (for any delta >0). This turns out to be optimal, under the exponential time hypothesis (ETH). Our core-set analysis is based on studying random-induced sub-problems of optimization problems. To the best of our knowledge, all the known results in our parameter range rely crucially on near-regularity assumptions. We avoid these by using a biased sampling approach, which we analyze using recent results on concentration of quadratic functions. We then show that our construction yields a 2-pass streaming (1+epsilon)-approximation for both problems; the algorithm uses O~(n^{1-delta}) space, for graphs of average degree n^delta.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sketching and sampling
Keywords
  • Sublinear algorithms
  • Streaming algorithms
  • Core-sets
  • Maximum cut
  • Correlation clustering

Metrics

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

Related Versions

References

  1. Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. Geometric approximation via coresets. Combinatorial and computational geometry, 52:1-30, 2005. Google Scholar
  2. Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semi-streaming model. In International Colloquium on Automata, Languages, and Programming, pages 328-338. Springer, 2009. Google Scholar
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st symposium on Principles of Database Systems, pages 5-14. ACM, 2012. Google Scholar
  4. KookJin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation clustering in data streams. In International Conference on Machine Learning, pages 2237-2246, 2015. Google Scholar
  5. Nir Ailon and Zohar Karnin. A note on: No need to choose: How to get both a ptas and sublinear query complexity. arXiv preprint arXiv:1204.6588, 2012. Google Scholar
  6. Noga Alon, W Fernandez De La Vega, Ravi Kannan, and Marek Karpinski. Random sampling and approximation of max-csps. Journal of computer and system sciences, 67(2):212-243, 2003. Google Scholar
  7. Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of the testable graph properties: it’s all about regularity. SIAM Journal on Computing, 39(1):143-167, 2009. Google Scholar
  8. Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 363-372. IEEE, 2011. Google Scholar
  9. Alexandr Andoni, Robert Krauthgamer, and David P Woodruff. The sketching complexity of graph cuts. arXiv preprint arXiv:1403.7058, 2014. Google Scholar
  10. Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of np-hard problems. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 284-293. ACM, 1995. Google Scholar
  11. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56(1-3):89-113, 2004. Google Scholar
  12. Boaz Barak, Moritz Hardt, Thomas Holenstein, and David Steurer. Subsampling mathematical relaxations and average-case complexity. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, pages 512-531, Philadelphia, PA, USA, 2011. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2133036.2133077.
  13. Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58-75, 2005. Google Scholar
  14. Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for max cut. Random Structures &Algorithms, 20(3):403-440, 2002. Google Scholar
  15. Dimitris Fotakis, Michael Lampis, and Vangelis Th Paschos. Sub-exponential approximation schemes for csps: from dense to almost sparse. arXiv preprint arXiv:1507.04391, 2015. Google Scholar
  16. Alan Frieze and Ravi Kannan. The regularity lemma and approximation schemes for dense problems. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 12-20. IEEE, 1996. Google Scholar
  17. Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1167-1176. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  18. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. Graph sparsification via refinement sampling. arXiv preprint arXiv:1004.4915, 2010. Google Scholar
  19. Ashish Goel, Michael Kapralov, and Ian Post. Single pass sparsification in the streaming model with edge deletions. arXiv preprint arXiv:1203.4900, 2012. Google Scholar
  20. Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653-750, 1998. Google Scholar
  21. Hossein Jowhari, Mert Sağlam, and Gábor Tardos. Tight bounds for lp samplers, finding duplicates in streams, and related problems. In Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 49-58. ACM, 2011. Google Scholar
  22. Michael Kapralov. Better bounds for matchings in the streaming model. In SODA, pages 1679-1697. SIAM, 2013. Google Scholar
  23. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from random streams. In SODA, pages 734-751. SIAM, 2014. Google Scholar
  24. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating max-cut. In SODA, pages 1263-1282. SIAM, 2015. Google Scholar
  25. Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker. (1+ ω (1))-approximation to max-cut requires linear space. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1703-1722. SIAM, 2017. Google Scholar
  26. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 561-570. IEEE, 2014. Google Scholar
  27. Jonathan A Kelner and Alex Levin. Spectral sparsification in the semi-streaming setting. Theory of Computing Systems, 53(2):243-262, 2013. Google Scholar
  28. Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proc. ITCS, pages 367-376. ACM, 2015. Google Scholar
  29. Claire Mathieu and Warren Schudy. Yet another algorithm for dense max cut: go greedy. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 176-182. Society for Industrial and Applied Mathematics, 2008. Google Scholar
  30. Morteza Monemizadeh and David P Woodruff. 1-pass relative-error lp-sampling with applications. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1143-1160. SIAM, 2010. Google Scholar
  31. Mark Rudelson and Roman Vershynin. Sampling from large matrices: An approach through geometric functional analysis. J. ACM, 54(4), 2007. URL: http://dx.doi.org/10.1145/1255443.1255449.
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 About DROPS Imprint Privacy Contact