Maintaining Matroid Intersections Online
Niv Buchbinder, Anupam Gupta, Daniel Hathcock, Anna R. Karlin, Sherry Sarkar · Society for Industrial and Applied Mathematics eBooks · 2024
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).