(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space

DOI10.1137/1.9781611974782.112zbMath1410.68169OpenAlexW4236077470MaRDI QIDQ4575855

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (5)

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 ⋮ Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ Fixed parameter tractability of graph deletion problems over data streams

This page was built for publication: (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space