Distributed set cover approximation: primal-dual with optimal locality

Recommendations

Optimal distributed covering algorithms
A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
A Local 2-Approximation Algorithm for the Vertex Cover Problem
A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds

Cites work

A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
A linear-time approximation algorithm for the weighted vertex cover problem
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
A threshold of ln n for approximating set cover
An Improved Distributed Algorithm for Maximal Independent Set
Distributed algorithms for covering, packing and maximum weighted matching
Distributed approximation of maximum independent set and maximum matching
Distributed Computing: A Locality-Sensitive Approach
scientific article; zbMATH DE number 6474898 (Why is no real title available?)
scientific article; zbMATH DE number 3869067 (Why is no real title available?)
scientific article; zbMATH DE number 1330032 (Why is no real title available?)
scientific article; zbMATH DE number 2086690 (Why is no real title available?)
Local computation: lower and upper bounds
Non-approximability results for optimization problems on bounded degree instances
On the complexity of local distributed graph problems
On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
On the hardness of approximating minimization problems
On the hardness of approximating minimum vertex cover
Some optimal inapproximability results
Survey of local algorithms
The design of approximation algorithms
The price of being near-sighted
Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(11)

Optimal distributed covering algorithms
Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
Tight bounds on the round complexity of the distributed maximum coverage problem
Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
Optimal Distributed Covering Algorithms
Rapid randomized pruning for fast greedy distributed algorithms
Beep-and-sleep: message and energy efficient set cover
Optimal distributed covering algorithms
A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership

This page was built for publication: Distributed set cover approximation: primal-dual with optimal locality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090914)