Randomized Composable Core-sets for Distributed Submodular Maximization

DOI10.1145/2746539.2746624zbMath1321.68361arXiv1506.06715OpenAlexW2037568170MaRDI QIDQ2941499

Morteza Zadimoghaddam, Vahab S. Mirrokni

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmsstreaming algorithmssubmodular maximizationcore-setsMapReduce algorithmsrandomized composable core-sets

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (10)

Fast Distributed Approximation for Max-Cut ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ Unnamed Item ⋮ Improved Algorithms for Time Decay Streams ⋮ Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ Unnamed Item ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ Distributed algorithms for matching in hypergraphs

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Randomized Composable Core-sets for Distributed Submodular Maximization