Tight bounds on the round complexity of the distributed maximum coverage problem

MaRDI QIDQ4608050zbMATH OpenFDO

Authors Sepehr Assadi, Sanjeev Khanna

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1801.02793, http://dl.acm.org/citation.cfm?id=3175460

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Recommendations

• Distributed set cover approximation: primal-dual with optimal locality
• scientific article; zbMATH DE number 6905172
• Better streaming algorithms for the maximum coverage problem
• Beep-and-sleep: message and energy efficient set cover
• Distributed algorithms for covering, packing and maximum weighted matching

Cited in

(8)

• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• Tight bounds for double coverage against weak adversaries
• Equivalence classes and conditional hardness in massively parallel computations
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Tight Bounds for Double Coverage Against Weak Adversaries
• Tight bounds for single-pass streaming complexity of the set cover problem
• scientific article; zbMATH DE number 2086678 (Why is no real title available?)
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds

This page was built for publication: Tight bounds on the round complexity of the distributed maximum coverage problem

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