A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds.
Reuven Bar-YehudaKeren Censor-HillelGregory SchwartzmanPublished in: PODC (2016)
Keyphrases
- log log
- vertex cover
- approximation algorithms
- positive integer
- polynomial time approximation
- np hard
- undirected graph
- agnostic learning
- special case
- precedence constraints
- approximation ratio
- affine transform
- partial order
- error bounds
- planar graphs
- optimality criterion
- uniform distribution
- information theoretic
- decision trees