Basic Information
Submodular Functions, Which Capture The Property of Diminishing Returns, Are Ubiquitous in Various Disciplines, Including Combinatorics, Graph Theory, Machine Learning, Economics, Algorithmic Game Theory, and Information Theory. The Family of Submodular Maximization and Minimization Problems Is a Prime Example of A Unified Approach That Captures Both Well-known Classic Problems, E.g., Max-cut, Max-dicut, and Generalized Assignment, and Real-world Applications in Diverse Settings, E.g., Information Gathering, Image Segmentation, Viral Marketing in Social Networks, and Recommendation Systems. This Course Deals With The Algorithmic Foundations of Submodular Optimization, Focusing On Basic Problems and Algorithmic Techniques. Learning Outcomes# at The End Of The Course The Students Will Be Able To# 1. Understand Basic Properties of Submodular Functions. 2. Design and Analyze Algorithms For Submodular Optimization. 3. Use Combinatorial, Randomized, and Continuous Techniques For Submodular Optimization. 4. Modeling Optimization Problems As Submodular.
Faculty: Computer Science
|Undergraduate Studies
|Graduate Studies
Pre-required courses
(94412 - Probability (advanced) and 234247 - Algorithms 1 and 236343 - Theory of Computation) or 104034 - Introduction to Probability H or 104222 - Probability Theory