Streaming Lower Bounds for Approximating MAX-CUT

DOI10.1137/1.9781611973730.84zbMath1371.68213arXiv1409.2138OpenAlexW2952096125MaRDI QIDQ5363106

Sanjeev Khanna, Michael Kapralov

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.2138

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (9)

Fast Distributed Approximation for Max-Cut ⋮ New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory ⋮ Unnamed Item ⋮ New bounds for the CLIQUE-GAP problem using graph decomposition theory ⋮ Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Streaming approximation resistance of every ordering CSP ⋮ (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond

This page was built for publication: Streaming Lower Bounds for Approximating MAX-CUT