Randomized composable core-sets for distributed submodular maximization

DOI10.1145/2746539.2746624zbMATH Open1321.68361arXiv1506.06715OpenAlexW2037568170MaRDI QIDQ2941499FDOQ2941499

Authors: 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)

Abstract: An effective technique for solving optimization problems over massive data sets is to partition the data into smaller pieces, solve the problem on each piece and compute a representative solution from it, and finally obtain a solution inside the union of the representative solutions for all pieces. This technique can be captured via the concept of {em composable core-sets}, and has been recently applied to solve diversity maximization problems as well as several clustering problems. However, for coverage and submodular maximization problems, impossibility bounds are known for this technique cite{IMMM14}. In this paper, we focus on efficient construction of a randomized variant of composable core-sets where the above idea is applied on a {em random clustering} of the data. We employ this technique for the coverage, monotone and non-monotone submodular maximization problems. Our results significantly improve upon the hardness results for non-randomized core-sets, and imply improved results for submodular maximization in a distributed and streaming settings. In summary, we show that a simple greedy algorithm results in a $1/3$-approximate randomized composable core-set for submodular maximization under a cardinality constraint. This is in contrast to a known $O(logkoversqrtk)$ impossibility result for (non-randomized) composable core-set. Our result also extends to non-monotone submodular functions, and leads to the first 2-round MapReduce-based constant-factor approximation algorithm with $O(n)$ total communication complexity for either monotone or non-monotone functions. Finally, using an improved analysis technique and a new algorithm $mathsfPseudoGreedy$, we present an improved $0.545$-approximation algorithm for monotone submodular maximization, which is in turn the first MapReduce-based algorithm beating factor $1/2$ in a constant number of rounds.

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

Recommendations

• Distributed submodular maximization
• The power of subsampling in submodular maximization
• Submodular maximization with cardinality constraints
• Techniques for submodular maximization
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity

zbMATH Keywords

distributed algorithmsstreaming algorithmssubmodular maximizationcore-setsMapReduce algorithmsrandomized composable core-sets

Mathematics Subject Classification ID

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

Cites Work

• Shortest-path queries in static networks
• Approximate distance oracles
• 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
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Approximate distance oracles with constant query time
• Fast C-K-R partitions of sparse graphs
• Automata, Languages and Programming
• Ramsey partitions and proximity data structures

Cited In (11)

• Fast Distributed Approximation for Max-Cut
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Submodular optimization in the MapReduce model
• Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
• Online submodular welfare maximization: greedy beats 1/2 in random order
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Distributed submodular maximization
• Improved Algorithms for Time Decay Streams
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Distributed algorithms for matching in hypergraphs
• Projection-free decentralized online learning for submodular maximization over time-varying networks

Uses Software

• Graphs

This page was built for publication: Randomized composable core-sets for distributed submodular maximization

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