Considering the model of computing under uncertainty where element weights axe uncertain but can be obtained at a cost by query operations, we study the problem of identifying a cheapest (minimum-weight) set among a given collection of feasible sets using a minimum number of queries of element weights. For the general case we present an algorithm that makes at most d · OPT + d queries, where d is the maximum cardinality of any given set and OPT is the optimal number of queries needed to identify a cheapest set. For the minimum multi-cut problem in trees with d terminal pairs, we give an algorithm that makes at most d · OPT + 1 queries. For the problem of computing a minimum-weight base of a given matroid, we give an algorithm that makes at most 2 · OPT queries, generalizing a known result for the minimum spanning tree problem. For each of our algorithms we give matching lower bounds.
展开▼
