Coresets for Robust Submodular Maximization with Deletions

Explore submodular maximization with deletions in this 39-minute conference talk by Nikolaj Tatti from the Finnish Center for Artificial Intelligence FCAI. Delve into robust submodular optimization methods addressing unexpected deletions due to privacy issues or user preferences. Learn about a single-pass streaming algorithm yielding approximation guarantees under p-matroid constraints and an offline algorithm with stronger approximation ratios. Discover the minimum number of items an algorithm must remember to achieve non-trivial approximation against adversarial deletion. Examine topics including optimization problems, submodularity, constraints, computational complexity, and experimental results. Gain insights from Tatti, an assistant professor at the University of Helsinki with extensive experience in data mining, statistical modeling, and optimization algorithms.

Intro
Example
Optimization problem
Submodularity
Constraints
Adversary
Computational complexity
Algorithms
RExc, robust streaming algorithm
Guarantees
Offline algorithm
Experiments
Running time