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

Reuven Bar-Yehuda Keren Censor-Hillel Gregory Schwartzman

Published in: CoRR (2016)

Keyphrases

log log
vertex cover
approximation algorithms
positive integer
polynomial time approximation
undirected graph
np hard
minimum cost
special case
agnostic learning
approximation ratio
affine transform
error bounds
upper bound
partial order
linear programming relaxation
sample size