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

Michael Kapralov Sanjeev Khanna Madhu Sudan Ameya Velingker

Published in: SODA (2017)

Keyphrases

linear space
max cut
nearest neighbor search
external memory
planar graphs
evolutionary algorithm
np hard
graph model
graph partitioning