报告地点：行健楼学术活动室526
摘要：The sheer scale of modern datasets has resulted in a dire need for summarization techniques that can identify representative elements in a dataset. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which could be near-optimally solved using greedy techniques in linear time. We consider a two-stage submodular framework where the goal is to use some given training functions to reduce the ground set so that optimizing new functions over the reduced set provides almost as much value as optimizing them over the entire ground set. In this talk, we design an approximation algorithm with constant approximation ratio with respect to the curvature, which improves the previous bound. In addition, we give a new streaming solution to this problem.
