Research map / Learning theory and algorithms / Combinatorial and search optimization
Accelerating Matroid Optimization through Fast Imprecise Oracles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies matroid maximum-weight basis computation in a two-oracle model with a fast dirty (imprecise) independence oracle and a costly clean oracle, giving robust algorithms whose clean-query count depends on prediction error and matching lower bounds.
Problem
Computing a maximum-weight basis of a matroid when clean independence queries are expensive and a fast dirty oracle may be imprecise; minimize clean-oracle calls.
Approach
Uses a dirty matroid's optimal basis as a prediction, then alternately adds and removes elements with binary and linear searches, with error measured by modification distance (additions and removals needed to turn the dirty basis into a clean max-weight basis); a robustified variant bounds worst-case queries by (1+1/k)n.
Key results
- Unweighted basis algorithm uses at most min{n-r+k+eta_A+eta_R(k+1)ceil(log2 r_d), (1+1/k)n} clean oracle calls.
- Weighted max-weight basis algorithm uses at most min{n-r+k+eta_A(k+1)+eta_R(k+1)ceil(log2 r_d), (1+1/k)n} clean oracle calls.
- Lower bounds show n-r+eta_A and n-r+eta_R*ceil(log2 r_d) clean queries are necessary for deterministic algorithms, so the bounds are essentially best possible.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the dirty oracle alongside the clean oracle, with robustness parameter k | Maximum-weight matroid basis optimization · Maximum-weight matroid basis | clean-oracle calls: n -> min\{n-r+k+ \eta_A \cdot (k+1)+\eta_R \cdot (k+1)\ceil{\log_2 r_d} , (1+\frac{1}{k})n\} | Helped |
| Use the dirty oracle alongside the clean oracle, with robustness parameter k | Unweighted matroid basis computation · Unweighted matroid basis | clean-oracle calls: n -> \min\{ n-r+k+\eta_A+ \eta_R \cdot (k+1)\lceil \log_2 r_d \rceil,(1+\frac{1}{k}) n\} | Helped |
| Use a maximum-weight dirty basis and binary-search-based modifications | Maximum-weight matroid basis optimization · Maximum-weight matroid basis | clean-oracle calls: n -> n- r + 1 + 2\eta_A + \eta_R \cdot \ceil{\log_2(r_d)} | Helped |
| Use a clean rank oracle rather than only independence queries | Unweighted matroid basis computation · Unweighted matroid basis | clean oracle calls: n+1 -> \min\big\{ n+1, \, 2 + \eta_R \cdot \ceil{\log_2 r_d} + \min \big\{ \eta_A \cdot \ceil{\log_2(n- r_d)}, \, n - r_ | Helped |
| Use dirty-oracle calls during augmentation | Matroid intersection · Matroid intersection | clean-oracle calls: (r+1) \cdot (2 + (\eta_1 + \eta_2) \cdot (\ceil{\log_2 (n)} +2)) | Helped |
| Warm-start from an optimum dirty solution, then remove elements until feasible | Matroid intersection · Matroid intersection | clean-oracle calls: 2 + 2 \eta_r \cdot (1 + \ceil{\log_2 (n)} ) | Helped |
Surprising findings
- For the weighted case, the error-dependent bound cannot match the unweighted one: a lower bound shows the unweighted guarantee is not achievable with max weight, separating the two settings.
- Using rank oracles, the dependence on n-r can be bypassed, achieving at most n+1 rank queries in the worst case.
Limitations
- Assumes dirty oracle calls are free; costly dirty calls require different algorithms.
- Analysis is theoretical with no experimental evaluation reported in the text.
Experimental setup
Metrics: number of clean oracle calls consistency robustness
Baselines: greedy algorithm simple algorithm error-dependent algorithm
Builds on: Edmonds greedy algorithm Kruskal's algorithm learning-augmented algorithms Bai and Coester two-oracle sorting
Closest papers by meaning
- Matroid Semi-Bandits in Sublinear Time (ICML 2024 · similarity 0.86)
- Improved Algorithms for Fair Matroid Submodular Maximization (NeurIPS 2025 · similarity 0.85)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.84)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.84)
- Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity (ICML 2025 · similarity 0.84)
- A Unified Approach to Submodular Maximization Under Noise (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.