Sketching and Randomization for Distributed Submodular and Coverage Optimization

on YouTube ↗39m

" summary

Randomized composable coresets plus sketching produce practical two‑round MapReduce and streaming algorithms for large coverage and submodular problems. Key claims: arbitrary partitioning suffices for diversity and capacitated clustering; adversarial partitioning forces a √K lower bound for submodular coresets, while random partitioning plus local greedy gives 1/3 and a tweaked pipeline (send items to O(1/ε) machines, coresets of size 4K) reaches ≈58%. For coverage, a dependent hashing sketch yields space depending only on number of sets and, on some graphs, a 3% sketch recovers ~96–99.6% of single‑machine quality. Tools: composable coresets, greedy, dependent rounding; two–three rounds and linear communication.

AI-written summary · about

" chapters (25)

1. 0:00Intro
2. 0:30Our team: Google NYC Algorithms Research Teams
3. 1:15Three most populal techniques applied in our tools
4. 3:03Composable Core-Sets for Distributed Optimization
5. 5:43Application in MapReduce/Distributed Computation
6. 6:14Application in Streaming Computation
7. 7:12Overview of recent theoretical results
8. 8:49Applications: Diversity & Submodular Maximization
9. 9:58Five Problems Considered
10. 11:00Diversity Maximization Problem
11. 11:49Core-sets for Diversity Maximization
12. 12:23Composable Core-set Results for Diversity Maximization
13. 12:56Distributed Clustering Problems
14. 13:40Mapping Core-sets for Capacitated Clustering
15. 14:39Empirical study for distributed clustering
16. 17:01Randomization to the Rescue: Randomized Core-sets
17. 18:27Results for Submodular Maximization: MZ (STOC 15)
18. 24:20Problem Formulation: Coverage Problems
19. 25:49Submodular Maximization vs. Coverage Maximization
20. 28:37Sketching Coverage Functions
21. 29:31Results for coverage problems
22. 33:03Approach
23. 33:34Sketching Technique
24. 36:44Feature Selection (ongoing)
25. 37:26Summary: Distributed Algorithms for Five Problems

" related talks

• 30mParallelization by ApproximationKanat Tangwongsan · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 35mDistributed Vertex Cover ReconfigurationYannic Maus, Keren Censor-Hillel, Shahar Romem-Peled, Tigran Tonoyan · ITCS 2022
• 53mMapReduce AlgorithmicsSergei Vassilvitskii · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 46mDistributed Graph Techniques in the MPC ModelQuanquan C. Liu · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 31mSome Novel Computational Models to Think AboutD Sivakumar · Information Theory in Complexity Theory and Combinatorics 2015
• 01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation AlgorithmsMohsen Ghaffari · Sublinear Algorithms Boot Camp 2024
• 10mQuery, Communication and DiscrepancyMakrand Sinha · Meet the Fellows Welcome Event
• 01h 05mGraph Algorithms in the MPC ModelSlobodan Mitrovic · Sublinear Algorithms Boot Camp 2024