A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(\log N\log \varDelta /\log ^2\log \varDelta ) Rounds.
Ran Ben-BasatGuy EvenKen-ichi KawarabayashiGregory SchwartzmanPublished in: SIROCCO (2018)
Keyphrases
- log log
- vertex cover
- approximation algorithms
- positive integer
- polynomial time approximation
- np hard
- undirected graph
- approximation guarantees
- approximation ratio
- agnostic learning
- special case
- worst case
- decision trees
- error bounds
- planar graphs
- affine transform
- precedence constraints
- shortest path
- affine invariance