Maintaining Matroid Intersections Online

Maintaining a maximum bipartite matching online while minimizing augmentations is a well studied problem, motivated by content delivery, job scheduling, and hashing. A breakthrough result of Bernstein, Holm, and Rotenberg (SODA 2018) resolved this problem up to a logarithmic factors. However, to model other problems in scheduling and resource allocation, we may need a richer class of combinatorial constraints (e.g., matroid constraints). We consider the problem of maintaining a maximum independent set of an arbitrary matroid M and a partition matroid P. Specifically, at each timestep t one part Pt of the partition matroid is revealed: we must now select at most one newly-revealed element, but may exchange some previously selected elements, to maintain a maximum independent set on the elements seen thus far. The goal is to minimize the number of augmentations. If M is also a partition matroid, we recover the problem of maintaining a maximum bipartite matching online with recourse as a special case. Our main result is an O(nlog² n)-competitive algorithm, where n is the rank of the largest common base; this matches the current best quantitative bound for the bipartite matching special case. Our result builds substantively on the result of Bernstein, Holm, and Rotenberg: a key contribution of our work is to make use of market equilibria and prices in submodular utility allocation markets.