Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with ApplicationsResearch Paper
A sensitivity oracle preprocesses a graph once so that, after a batch of at most edge failures or insertions arrives, a question about the modified graph is answered without recomputing from scratch. Networks fail a few links at a time, and the planner wants the new maximum throughput, the new bottleneck cut, or the new cheapest routing at once. For…