A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds.

Reuven Bar-Yehuda Keren Censor-Hillel Gregory Schwartzman

Published in: J. ACM (2017)

Keyphrases

log log
vertex cover
approximation algorithms
positive integer
polynomial time approximation
undirected graph
np hard
special case
approximation ratio
agnostic learning
affine transform
partial order
precedence constraints
planar graphs
worst case
decision trees
log likelihood
minimum cost