Randomized Composable Core-Sets for Submodular Maximization

Explore randomized composable core-sets for distributed submodular and diversity maximization in this 33-minute lecture by Morteza Zadimoghaddam. Delve into an effective technique for solving optimization problems over massive data sets by partitioning data, solving problems on smaller pieces, and computing representative solutions. Learn about the concept of composable core-sets and its application to diversity maximization and clustering problems. Discover how randomization overcomes impossibility bounds for coverage and submodular maximization problems. Examine the simple greedy algorithm that results in a 1/3-approximate randomized composable core-set for submodular maximization under cardinality constraints. Investigate the extension to non-monotone submodular functions and its implications for MapReduce-based algorithms. Study the improved PseudoGreedy algorithm for monotone submodular maximization, achieving a 0.545-approximation. Gain insights into the importance of robust analysis, B-nice algorithms, and future research directions in this field of combinatorial optimization.

Intro
Outline
Processing Big Data
General Framework
Submodular Functions: example
Formal Definition of Composable Core-sets
Randomization Comes to Rescue
Importance of Robust Analysis
Family of B-nice Algorithms
Algorithm Greedy
Warm up: single machine greedy
Analysis of B-nice Algorithms
Upper Bounding A Differences
Remarks and Future work