Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut.

Sevag Gharibian Ojas Parekh

Published in: APPROX-RANDOM (2019)

Keyphrases

approximation algorithms
max cut
np hard
worst case
minimum cost
constant factor
optimal solution
special case
primal dual
dynamic programming
lower bound
np complete
undirected graph
approximation ratio
constant factor approximation
planar graphs
greedy algorithm
computational complexity