An optimal space lower bound for approximating MAX-CUT.

Michael Kapralov Dmitry Krachun

Published in: STOC (2019)

Keyphrases

lower bound
max cut
optimal solution
upper bound
worst case
branch and bound algorithm
competitive ratio
dynamic programming
branch and bound
np hard
objective function
multiscale
graphical models
vector space
min max
np complete problems