The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover.

Jon M. Kleinberg Michel X. Goemans

Published in: SIAM J. Discret. Math. (1998)

Keyphrases

semidefinite programming
vertex cover
semidefinite
approximation algorithms
primal dual
linear programming
optimality criterion
worst case
maximum margin
kernel matrix
precedence constraints
machine learning
pairwise
special case
branch and bound
planar graphs