Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs.

Sushant Sachdeva Rishi Saket

Published in: APPROX-RANDOM (2011)

Keyphrases

np hardness
vertex cover
approximation algorithms
np hard
worst case
optimality criterion
special case
optimal solution
mixed integer
evolutionary algorithm
precedence constraints
finding optimal
greedy heuristic
polynomial time approximation
knapsack problem
approximation guarantees
bayesian networks