Title: Online Submodular Maximization with Free Disposal

Speaker: Hubert Chan, University of Hong Kong

Time/Date: Friday, Apr 22, 11-12

Location: 3501

Abstract:

We study the online submodular maximization problem with free disposal
under a matroid constraint. Elements from some ground set arrive one
by one in rounds, and the algorithm maintains a feasible set that is
independent in the underlying matroid. In each round when a new
element arrives, the algorithm may accept the new element into its
feasible set and possibly remove elements from it, provided that the
resulting set is still independent. The goal is to maximize the value
of the final feasible set under some monotone submodular function.

We show that no deterministic monotone algorithm can be strictly
better than 0.25-competitive even for partition matroids, the most
modest generalization of k-uniform matroids, matching the competitive
ratio by Chakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP
2015). Interestingly, we prove that randomized algorithms are strictly
more powerful by giving a (non-monotone) randomized algorithm for
partition matroids with ratio 0.3178.

This is joint work with Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang
and Zhihao Gavin Tang.