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. Topics That Will Be Covered Include# Introduction To Submodularity, Submodular Maximization With a Cardinality Constraint, Unconstrained Submodular Maximization, Continuous Extensions Of Submodular Functions and Their Algorithmic Uses, and Submodular Minimization. Learning Outcomes# at The End of The Course The Students Will Be Able To# 1. Identify and Be Able to Solve Optimization Problems Involving Submodular Functions That They Will Encounter in Future Theoretical And Practical Research, As Well As Problems Arising While Working In The Industry._ 2. Apply The Knowledge Acquired Throughout The Course to Independently Design and Analyze Algorithms to New Submodular Optimization Problems They Encounter. 3. Proficient in Using Discrete, Randomized, and Continuous Techniques When Solving Algorithmic Problems.
Faculty: Computer Science
|Undergraduate Studies
|Graduate Studies
Pre-required courses
(94412 - Probability (advanced) and 234247 - Algorithms 1 and 236343 - Theory of Computation)