A Sharp Barrier of Consistent Submodular Maximization: Any Improvement over 2 − √2 Entails Exponential Queries or Linear RecourseResearch Paper
In consistent submodular maximization the elements of a finite ground set arrive one at a time, and an algorithm must maintain a set of at most arrived elements of high value for a monotone submodular objective , while changing only a few elements per arrival. The number of changes at time , the recourse , must stay below a…