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

zbMATH Open1403.68325arXiv1801.02793MaRDI QIDQ4608050FDOQ4608050

Authors: Sepehr Assadi, Sanjeev Khanna 

Publication date: 15 March 2018

Full work available at URL: https://arxiv.org/abs/1801.02793

Recommendations

• Distributed set cover approximation: primal-dual with optimal locality
• scientific article
• 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

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)

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
• Title not available (Why is that?)
• 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)