Explore a lecture on maximizing monotone submodular functions over the integer lattice, presented by Tasuku Soma at the Hausdorff Center for Mathematics. Delve into polynomial time approximation algorithms for various constraints and their applications in machine learning tasks. Learn about the limitations of set functions, definitions of submodularity, and the concept of DR-submodularity. Discover algorithms for cardinality and polymatroid constraints, as well as DR-submodular cover problems. Gain insights into the powerful framework of monotone submodular function maximization and its relevance to diverse machine learning problems in this 30-minute talk, part of the Hausdorff Trimester Program on Combinatorial Optimization.
Maximizing Monotone Submodular Functions over the Integer Lattice
Hausdorff Center for Mathematics via YouTube
Overview
Syllabus
Intro
Monotone Submodular Func Maximization
Limitation of Set Function
Definitions of Submodularity on 2
Monotone Submod Func Maximization on 2
Can We Reduce it to Set Function? YES, if is DR-submodular.
Our Results
Algorithms
Cardinality/DR-Submodular
Cardinality/Lattice-Submodular Idea: Devide the range into polynomially many regions.
Polymatroid/DR-Submodular
DR-Submodular Cover
Summary
Taught by
Hausdorff Center for Mathematics
