On the integrality ratio of semidefinite relaxations of MAX CUT.

Uriel Feige Gideon Schechtman

Published in: STOC (2001)

Keyphrases

semidefinite
max cut
semidefinite programming
graph model
planar graphs
convex relaxation
np hard
sufficient conditions
linear programming relaxation
higher dimensional
mixed integer
convex sets
linear systems
interior point methods
linear programming
multi label
support vector machine
evolutionary algorithm