Submodular Optimization and Applications
Abstract: The family of submodular optimization problems is a prime example of a unified approach, whose goal is to create a single framework, that on one hand is general enough to capture many new and exciting real-world applications in diverse disciplines, e.g., machine learning and economics, and on the other hand admits a mathematically rich and deep structure.
In this talk we discuss novel techniques to submodular maximization problems by considering several core problems: unconstrained submodular maximization, maximization given a cardinality constraint, and fractional maximization. We resolve the former problem, obtaining a linear time algorithm with an information theoretic tight guarantee, while for the other two we present unified algorithms that work for all cases achieving improved, and in some cases information theoretic tight, guarantees.
Our approaches to these problems employ a combination of probabilistic and combinatorial techniques.