  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, to which the algorithm has oracle access.
  For $k$-uniform matroids, we give a deterministic algorithm with competitive
ratio at least $0.2959$, and the ratio approaches $\frac{1}{\alpha_\infty}
\approx 0.3178$ as $k$ approaches infinity, improving the previous best ratio
of $0.25$ by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015)
and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimal
among a class of deterministic monotone algorithms that accept a new arriving
element only if the objective is strictly increased.
  Further, we prove 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 show that randomized algorithms are strictly more powerful by
giving a (non-monotone) randomized algorithm for partition matroids with ratio
$\frac{1}{\alpha_\infty} \approx 0.3178$.
