Huy Nguyen
Fast submodular maximization via approximate data structures

Abstract: We consider the problem of maximizing a submodular function
subject to a partition matroid constraint or a graphic matroid
constraint. Submodular functions capture many classes of functions
including graph cut, coverage functions, Shannon entropy and
log-determinants and they are used as objective functions in a variety
of applications from sensor placement to text summarization and
influence maximization. In this talk, we describe a nearly linear time
algorithm for the problem with a near optimal approximation of
1-1/e-epsilon. The algorithm is based on fast data structures for
maintaining an approximate maximum weight base of the matroid. Joint
work with Alina Ene.