How Good is the Goemans-Williamson MAX CUT Algorithm?

Howard J. Karloff

Published in: SIAM J. Comput. (1999)

Keyphrases

max cut
computational complexity
np hard
randomly generated
k means
genetic algorithm
optimal solution
expectation maximization
search space
segmentation algorithm
graph partitioning
min max
greedy heuristic