Randomized composable core-sets for distributed submodular maximization

DOI10.1145/2746539.2746624MaRDI QIDQ2941499zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(11)

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

Describes a project that uses

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)