Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2-epsilon

Published in: Electron. Colloquium Comput. Complex. (2001)

Keyphrases

vertex cover
planar graphs
approximation algorithms
partial order
precedence constraints
optimality criterion
undirected graph
scheduling problem
worst case
graph theory
weighted graph
special case
graphical models
directed graph
piecewise linear