Date/Time:20 Mar 2019 15:00Venue: S17 #05-12 SR4Speaker: Jonathan Mark Scarlett, National University of SingaporeRobust Submodular Function MaximizationIn the first part of this talk, I will give a brief introduction to a “diminishing returns” property of set functions known as submodularity, and overview some applications and classical guarantees of greedy optimization methods. In the second part, I will turn to a robust variation of the submodular optimization problem in which some of the selected elements of the set are removed by an adversary, and we want the function value to remain as a high as possible even after these removals. We introduce an algorithm based on applying the greedy subroutine to carefully defined partitions, and provide a theoretical guarantee of attaining a constant-factor approximation of the best valueAdd to calendar:
