Maintaining Matroid Intersections Online

Niv Buchbinder, Anupam Gupta, Daniel Hathcock, Anna R. Karlin, Sherry Sarkar

Research output: Contribution to conferencePaperpeer-review


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(nlog2 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.

Original languageEnglish (US)
Number of pages22
StatePublished - 2024
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: Jan 7 2024Jan 10 2024


Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Maintaining Matroid Intersections Online'. Together they form a unique fingerprint.

Cite this