Title: Approximation Algorithms for Online Weighted Rank Function
Maximization under Matroid Constraints
 
Abstract: Consider the following online version of the submodular
maximization problem under a matroid constraint. We are given a set of
elements over which a matroid is defined. The goal is to incrementally
choose a subset that remains independent in the matroid over time. At
each time, a new submodular function over the same elements is
presented; the algorithm can add a few elements to the incrementally
constructed set, and reaps a reward equal to the value of the
submodular function on the current set. The goal of the algorithm as
it builds this independent set online is to maximize the sum of these
rewards. This problem is a natural extension of two well-studied
streams of earlier work: the first is on online set cover algorithms
(in particular for the max coverage version) while the second is on
approximately maximizing submodular functions under a matroid
constraint.  In this paper, we present the first randomized online
algorithms for this problem with poly-logarithmic competitive ratio
when each of the submodular function is a weighted rank function of a
matroid. To do this, we first solve a LP relaxation for the problem in
an online manner. This involves using uncrossing properties of tight
sets in the matroid polytope crucially with the primal-dual schema. We
then give a randomized algorithm that produces a sufficiently large
reward independent set. To achieve this, we prove and use new covering
properties for randomly rounded fractional solutions in the matroid
polytope that may be of independent interest. Joint work with Niv
Buchbinder, Seffi Naor and R. Ravi.