Rapid randomized pruning for fast greedy distributed algorithms

DOI10.1145/1835698.1835777zbMath1315.68274OpenAlexW1991337804MaRDI QIDQ5176209

Saurav Pandit, Sriram V. 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

facility locationrandomized algorithmsdistributed algorithmsgreedy algorithmsprimal-dual algorithms\textsc{Minimum Dominating Set}

Mathematics Subject Classification ID

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

Related Items (3)

Towards the price of leasing online ⋮ Lessons from the congested clique applied to MapReduce ⋮ Sub-logarithmic distributed algorithms for metric facility location

Uses Software

• CCSTM

Cites Work

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

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