# The minimum cost query problem on matroids with uncertainty areas

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2019.

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

- [Sorting and Hypergraph Orientation under Uncertainty with Predictions](https://mlsanity.com/paper/2305.09245/) (2023)
- [Geometric Preference Elicitation for Minimax Regret Optimization in Uncertainty Matroids](https://mlsanity.com/paper/2503.18668/) (2025)
- [Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations](https://mlsanity.com/paper/2610.14996/) (2026)

## Abstract (arXiv)

We study the minimum weight basis problem on matroid when elements' weights are uncertain. For each element we only know a set of possible values (an uncertainty area) that contains its real weight. In some cases there exist bases that are uniformly optimal, that is, they are minimum weight bases for every possible weight function obeying the uncertainty areas. In other cases, computing such a basis is not possible unless we perform some queries for the exact value of some elements. Our main result is a polynomial time algorithm for the following problem. Given a matroid with uncertainty areas and a query cost function on its elements, find the set of elements of minimum total cost that we need to simultaneously query such that, no matter their revelation, the resulting instance admits a uniformly optimal base. We also provide combinatorial characterizations of all uniformly optimal bases, when one exists; and of all sets of queries that can be performed so that after revealing the corresponding weights the resulting instance admits a uniformly optimal base.