Submodular Optimization: Variants, Theory and Applications

Submodular function optimization is a fundamental tool in modeling complex interactions in machine learning and graph mining problems. We propose to study constrained submodular optimization to improve the current state of the art. Our goals are to design evolutionary algorithms with stronger approximation guarantees, the study of submodular maximization under submodular constraints, fairness in submodular optimization, and k-submodular optimization. We begin by exploring a basic submodular maximization problem in the context of viral marketing/information diffusion in social networks. From there, we broaden our scope to include a broader range of scenarios and formulate them into more optimization problems. Looking ahead, we plan to tackle scalable submodular optimization problems in fairness, dynamic constraints, dynamic streams, and distributed fashion. Lastly, we discuss a series of real-world applications that can be formulated as submodular optimization problems. In the future, we aim to apply algorithmic ideas to solve more real-world problems.