# Accelerating Matroid Optimization through Fast Imprecise Oracles

arXiv: https://arxiv.org/abs/2402.02774 · HTML: https://mlsanity.com/paper/2402.02774/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 5 Feb 2024.

## Builds on (most cited first, 25 of 25)

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Active Learning from Weak and Strong Labelers](https://mlsanity.com/paper/1510.02847/) (2015)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Submodular Optimization under Noise](https://mlsanity.com/paper/1601.03095/) (2016)
- [Facility Location in Evolving Metrics](https://mlsanity.com/paper/1403.6758/) (2014)
- [Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty](https://mlsanity.com/paper/2206.15201/) (2022)
- [Faster Matroid Intersection](https://mlsanity.com/paper/1911.10765/) (2019)
- [Active Learning for Noisy Data Streams Using Weak and Strong Labelers](https://mlsanity.com/paper/2010.14149/) (2020)
- [Metric Clustering and MST with Strong and Weak Distance Oracles](https://mlsanity.com/paper/2310.15863/) (2023)
- [Changing Bases: Multistage Optimization for Matroids and Matchings](https://mlsanity.com/paper/1404.3768/) (2014)
- [Online Multistage Subset Maximization Problems](https://mlsanity.com/paper/1905.04162/) (2019)
- [Rate distortion optimization over large scale video corpus with machine learning](https://mlsanity.com/paper/2008.12408/) (2020)
- [Efficient Submodular Optimization under Noise: Local Search is Robust](https://mlsanity.com/paper/2210.11992/) (2022)
- [Fast Algorithms via Dynamic-Oracle Matroids](https://mlsanity.com/paper/2302.09796/) (2023)
- [Faster Matroid Partition Algorithms](https://mlsanity.com/paper/2303.05920/) (2023)
- [Sorting and Hypergraph Orientation under Uncertainty with Predictions](https://mlsanity.com/paper/2305.09245/) (2023)
- [On the Tradeoff between Stability and Fit](https://mlsanity.com/paper/1302.2137/) (2013)
- [Approximating Multistage Matching Problems](https://mlsanity.com/paper/2002.06887/) (2020)
- [Multistage s-t Path: Confronting Similarity with Dissimilarity](https://mlsanity.com/paper/2002.07569/) (2020)
- [Breaking O(nr) for Matroid Intersection](https://mlsanity.com/paper/2105.05673/) (2021)
- [A General Approach to Approximate Multistage Subgraph Problems](https://mlsanity.com/paper/2107.02581/) (2021)

## Built on by (most cited first, 3 of 3)

- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)

## Abstract (arXiv)

Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus, weaker models which give imprecise results quickly can be advantageous, provided inaccuracies can be resolved using few queries to a stronger model. In the fundamental problem of computing a maximum-weight basis of a matroid, a well-known generalization of many combinatorial optimization problems, algorithms have access to a clean oracle to query matroid information. We additionally equip algorithms with a fast but dirty oracle modelling an unknown, potentially different matroid. We design and analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty matroids, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. Further, we outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.