Speaker:Madhavan Rajagopal Padmanabhan

Constrained submodular optimization and applications in information diffusion

Optimization problems involving submodular functions naturally arise in a wide variety of application domains such as machine learning, sensor placement, and information diffusion. These problems often involve submodular cost constraints and cardinality constraints. In this talk, we will address two such problems: 1) SCSK-C: Maximize a submodular function with a submodular cost and cardinality constraint. 2) Diff-C: Maximize the difference between two submodular functions with a cardinality constraint. Although these problems are NP-Hard and inapproximable, we will discuss approximation algorithms with data-dependent additive errors. 

Join on WebEX: https://iastate.webex.com/iastate/j.php?MTID=me85a29a6d5ceac53f61f66674524b3af Meeting number: 2621 837 3678 Password: XYscqJjA374