(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

• An optimal space lower bound for approximating MAX-CUT
• Streaming Lower Bounds for Approximating MAX-CUT
• Sketching cuts in graphs and hypergraphs
• Sublinear algorithms for MAXCUT and correlation clustering
• Streaming and communication complexity of clique approximation

Mathematics Subject Classification ID

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 (8)

• 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
• Intractability of min- and max-cut in streaming graphs
• Streaming and communication complexity of clique approximation
• Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

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)