Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Randomized Composable Core-Sets for Submodular Maximization

Hausdorff Center for Mathematics via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.

Syllabus

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

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of Randomized Composable Core-Sets for Submodular Maximization

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.