Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy.

Siavosh Benabbas Siu On Chan Konstantinos Georgiou Avner Magen

Published in: FSTTCS (2011)

Keyphrases

vertex cover
approximation algorithms
worst case
lower bound
partial order
precedence constraints
planar graphs
upper bound
special case
optimality criterion
polynomial time approximation
np hard
mixed integer
data points
scheduling problem
model selection