Distributed set cover approximation: Primal-dual with optimal locality
From MaRDI portal
Publication:5090914
DOI10.4230/LIPIcs.DISC.2018.22zbMath1497.68561OpenAlexW2899153618MaRDI QIDQ5090914
Mohsen Ghaffari, Moti Medina, Guy Even
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9811/pdf/LIPIcs-DISC-2018-22.pdf/
Related Items (2)
Optimal distributed covering algorithms ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed algorithms for covering, packing and maximum weighted matching
- On the hardness of approximating minimum vertex cover
- A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Survey of local algorithms
- The Design of Approximation Algorithms
- A threshold of ln n for approximating set cover
- Local Computation
- The price of being near-sighted
- A linear-time approximation algorithm for the weighted vertex cover problem
- On the hardness of approximating minimization problems
- Distributed Computing: A Locality-Sensitive Approach
- An Improved Distributed Algorithm for Maximal Independent Set
- A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
- On the complexity of local distributed graph problems
- Non-approximability results for optimization problems on bounded degree instances
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Distributed Approximation of Maximum Independent Set and Maximum Matching
- Some optimal inapproximability results
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
This page was built for publication: Distributed set cover approximation: Primal-dual with optimal locality
