Document Open Access Logo

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

Authors Venkatesan Guruswami, Ameya Velingker, Santhoshini Velusamy

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.8.pdf
  • Filesize: 0.54 MB
  • 19 pages

Document Identifiers

Author Details

Venkatesan Guruswami
Ameya Velingker
Santhoshini Velusamy

Cite As Get BibTex

Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.8

Abstract

We study the complexity of estimating the optimum value of a Boolean 2CSP (arity two constraint satisfaction problem) in the single-pass streaming setting, where the algorithm is presented the constraints in an arbitrary order. We give a streaming algorithm to estimate the optimum within a factor approaching 2/5 using logarithmic space, with high probability. This beats the trivial factor 1/4 estimate obtained by simply outputting 1/4-th of the total number of constraints.

The inspiration for our work is a lower bound of Kapralov, Khanna, and Sudan (SODA'15) who showed that a similar trivial estimate (of factor 1/2) is the best one can do for Max CUT. This lower bound implies that beating a factor 1/2 for Max DICUT (a special case of Max 2CSP), in particular, to distinguish between the case when the optimum is m/2 versus when it is at most (1/4+eps)m, where m is the total number of edges, requires polynomial space. We complement this hardness result by showing that for DICUT, one can distinguish between the case in which the optimum exceeds (1/2+eps)m and the case in which it is close to m/4.

We also prove that estimating the size of the maximum acyclic subgraph of a directed graph, when its edges are presented in a single-pass stream, within a factor better than 7/8 requires polynomial space.

Subject Classification

Keywords
  • approximation algorithms
  • constraint satisfaction problems
  • optimization
  • hardness of approximation
  • maximum acyclic subgraph

Metrics

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

References

  1. Paola Alimonti. Non-oblivious local search for MAX 2-CSP with application to MAX DICUT. In 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, pages 2-14, 1997. Google Scholar
  2. András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n²) time. Proceedings of the 28th annual ACM symposium on Theory of computing, pages 47-55, 1996. Google Scholar
  3. Lars Engebretsen and Venkatesan Guruswami. Is constraint satisfaction over two variables always easy? Random Structures and Algorithms, 25(2):150-178, 2004. Google Scholar
  4. Uriel Feige and Michel X. Goemans. Aproximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In Third Israel Symposium on Theory of Computing and Systems (ISTCS), pages 182-189, 1995. URL: http://dx.doi.org/10.1109/ISTCS.1995.377033.
  5. Uriel Feige and Shlomo Jozeph. Oblivious algorithms for the Maximum Directed Cut problem. Algorithmica, 71(2):409-428, 2015. URL: http://dx.doi.org/10.1007/s00453-013-9806-z.
  6. Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC'07, pages 516-525, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1250790.1250866.
  7. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995. URL: http://dx.doi.org/10.1145/227683.227684.
  8. Venkatesan Guruswami and Euiwoong Lee. Towards a characterization of approximation resistance for symmetric CSPs. In Proceedings of Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM), pages 305-322, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.305.
  9. Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra. Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, pages 573-582, 2008. Google Scholar
  10. Venkatesan Guruswami and Yuan Zhou. Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set. Theory of Computing, 8(11):239-267, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a011.
  11. Eran Halperin and Uri Zwick. Combinatorial approximation algorithms for the maximum directed cut problem. In Proceedings of the 12th Annual Symposium on Discrete Algorithms, pages 1-7, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365412.
  12. Eran Halperin and Uri Zwick. Combinatorial approximation algorithms for the maximum directed cut problem. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'01, pages 1-7, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=365411.365412.
  13. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. URL: http://dx.doi.org/10.1145/502090.502098.
  14. Johan Håstad. Every 2-CSP allows nontrivial approximation. Computational Complexity, 17(4):549-566, 2008. URL: http://dx.doi.org/10.1007/s00037-008-0256-y.
  15. Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 53(3):307-323, May 2006. URL: http://dx.doi.org/10.1145/1147954.1147955.
  16. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming Lower Bounds for Approximating MAX-CUT. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 1263-1282, Philadelphia, PA, USA, 2015. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2722129.2722213.
  17. 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, SODA'17, pages 1703-1722, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3039686.3039798.
  18. Alantha Newman. Approximating the maximum acyclic subgraph. Master’s thesis, MIT, June 2000. Google Scholar
  19. D. A. Spielman and N. Srivastava. Graph sparsification by effective resistances. STOC, pages 563-568, 2008. Google Scholar
  20. Johan Thapper and Stanislav Zivny. The complexity of finite-valued CSPs. J. ACM, 63(4):37:1-37:33, 2016. URL: http://dx.doi.org/10.1145/2974019.
  21. Luca Trevisan. Parallel approximation algorithms by positive linear programming. Algorithmica, 21(1):72-88, 1998. URL: http://dx.doi.org/10.1007/PL00009209.
  22. Elad Verbin and Wei Yu. The streaming complexity of cycle counting, sorting by reversals, and other problems. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'11, pages 11-25, Philadelphia, PA, USA, 2011. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2133036.2133038.
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