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

YouTube

Quotient Sparsification for Submodular Functions

Simons Institute via YouTube

Overview

Explore a 29-minute lecture on quotient sparsification for submodular functions presented by Kent Quanrud from Purdue University at the Simons Institute. Delve into the unification of graph and hypergraph sparsification through a general theorem on sparsifying matroids and monotone submodular functions. Discover how this approach generalizes k-cuts in graphs and hypergraphs, and learn about its applications in preserving quotient weights in matroids, creating hypergraph cut sparsifiers, and reducing points in set systems while maintaining union weights. Examine algorithms for efficient sparsification of hypergraphs, set systems, and matroids in nearly linear time. Gain insights into this fresh perspective on optimization and algorithm design, which offers conceptual unity and practical applications in various areas of computer science and mathematics.

Syllabus

Quotient Sparsification for Submodular Functions

Taught by

Simons Institute

Reviews

Start your review of Quotient Sparsification for Submodular Functions

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.