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

YouTube

Recent Results on Maximizing Submodular Functions

Hausdorff Center for Mathematics via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore recent advancements in submodular maximization through this comprehensive lecture, covering both constrained and unconstrained scenarios, as well as monotone and non-monotone submodular functions. Delve into key concepts such as decreasing marginals, modular functions, and the value oracle model. Examine the differences between unconstrained and constrained optimization, and learn about the directed case and its historical context. Gain insights into greedy algorithms, randomization techniques, and relaxations, including the multilinear extension. Investigate constraints and their impact on optimization, and understand the continuous greedy algorithm and its application to the modular welfare problem. This in-depth presentation, part of the Hausdorff Trimester Program on Combinatorial Optimization, offers a thorough exploration of cutting-edge research in submodular function maximization.

Syllabus

Introduction
Definition
Decreasing Marginals
Modular Functions
Optimization
Value Oracle Model
Unconstrained vs Unconstrained
Submodular functions
Directed case
History
Greedy
Algorithm
Main Observation
Analysis
Randomization
Relaxations
MultiLinear Extension
Constraints
Continuous Greedy
Modular Welfare Problem
Continuous Greedy Algorithm

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of Recent Results on Maximizing 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.