Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds.

.Abstract: 

We study set selection problems where the weights are uncertain. Instead of its exact weight, only an uncertainty interval containing its true weight is available for each element.

In some cases, some solutions are universally optimal; i.e., they are optimal for every weight that lies within the uncertainty intervals.

However, it may be that no universally optimal solution exists, unless we are revealed additional information on the precise values of some elements.

In the minimum cost admissible query problem, we are tasked to (non-adaptively) find a minimum-cost subset of elements that, no matter how they are revealed, guarantee the existence of a universally optimal solution.

This belongs to the setting of explorable uncertainty and while there is a significant body of work in the adaptive setting, non-adaptive versions, such as the one in this paper, are far-less understood.

We provide efficient algorithms for finding minimum cost admissible queries thresholds in the settings of minimum spanning trees, matroids, and matchings in trees; and NP-hardness results in the settings of s-t shortest paths and bipartite matching.

We obtain our results by introducing thresholds under uncertainty. Roughly speaking, for every element e, there is a threshold for its weight, below which e is included in all optimal solutions and a second threshold above which e is excluded from all optimal solutions. We show that computing thresholds and finding minimum cost admissible queries are essentially equivalent problems. Thus, reducing the analysis of the minimum admissible query problem to the problem of computing thresholds.

Posted on Oct 14, 2024 in ACGO, Seminars