arXiv Open Access 2016

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

Reuven Bar-Yehuda Keren Censor-Hillel Gregory Schwartzman

Lihat Sumber

Abstrak

We present a simple deterministic distributed $(2+ε)$-approximation algorithm for minimum weight vertex cover, which completes in $O(\logΔ/ε\log\logΔ)$ rounds, where $Δ$ is the maximum degree in the graph, for any $ε>0$ which is at most $O(1)$. For a constant $ε$, this implies a constant approximation in $O(\logΔ/\log\logΔ)$ rounds, which contradicts the lower bound of [KMW10].

Topik & Kata Kunci

cs.DC cs.DS

Penulis (3)

Reuven Bar-Yehuda

Keren Censor-Hillel

Gregory Schwartzman

Format Sitasi

APA MLA BibTeX

Bar-Yehuda, R., Censor-Hillel, K., Schwartzman, G. (2016). A Distributed $(2+ε)$-Approximation for Vertex Cover in $O(\logΔ/ε\log\logΔ)$ Rounds. https://arxiv.org/abs/1602.03713

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2016
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓