Rapid randomized pruning for fast greedy distributed algorithms

DOI10.1145/1835698.1835777MaRDI QIDQ5176209zbMATH OpenOpenAlexFDO

Authors Saurav Pandit, Sriram Pemmaraju

Publication date 2 March 2015

Published in Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1835698.1835777

zbMATH Keywords

\textsc{Minimum Dominating Set}distributed algorithmsfacility locationgreedy algorithmsprimal-dual algorithmsrandomized algorithms

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15) Randomized algorithms (68W20) Continuous location (90B85)

Recommendations

• Return of the primal-dual, distributed metric facility location
• Fast Distributed Algorithms Via Primal-Dual (Extended Abstract)
• Super-fast distributed algorithms for metric facility location
• An efficient distributed algorithm for constructing small dominating sets
• Distributed set cover approximation: primal-dual with optimal locality

Cites work

• Elastic Transactions
• Software transactional memory
• Toward a theory of transactional contention managers

Cited in

(5)

• An efficient distributed thinning algorithm
• Towards the price of leasing online
• The message complexity of distributed graph optimization
• Sub-logarithmic distributed algorithms for metric facility location
• Lessons from the congested clique applied to MapReduce

Describes a project that uses

Uses Software

• CCSTM

This page was built for publication: Rapid randomized pruning for fast greedy distributed algorithms

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