(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space
DOI10.1137/1.9781611974782.112zbMATH Open1410.68169OpenAlexW4236077470MaRDI QIDQ4575855FDOQ4575855
Madhu Sudan, Ameya Velingker, Sanjeev Khanna, Michael Kapralov
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611974782.112
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25)
Cited In (6)
- Streaming approximation resistance of every ordering CSP
- Fixed parameter tractability of graph deletion problems over data streams
- Graph sketching and streaming: new approaches for analyzing massive graphs
- Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
- Sublinear Algorithms for MAXCUT and Correlation Clustering
- Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
This page was built for publication: (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575855)
