(1 + (1))-approximation to MAX-CUT requires linear space
DOI10.1137/1.9781611974782.112zbMATH Open1410.68169OpenAlexW4236077470MaRDI QIDQ4575855FDOQ4575855
Authors: Michael Kapralov, Sanjeev Khanna, Ameya Velingker, Madhu Sudan 
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
Recommendations
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 (11)
- Streaming approximation resistance of every ordering CSP
- Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
- 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
- Intractability of min- and max-cut in streaming graphs
- Sketching cuts in graphs and hypergraphs
- Streaming and communication complexity of clique approximation
- Optimal lower bounds for sketching graph cuts
- An optimal space lower bound for approximating MAX-CUT
- Sublinear algorithms for MAXCUT and correlation clustering
This page was built for publication: \((1 + \Omega(1))\)-approximation 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)
