An improved algorithm for selecting <Emphasis Type="Italic">p</Emphasis> items with uncertain returns according to the minmax-regret criterion

We consider the problem of selecting a subset of p investments of maximum total return out of a set of n available investments with uncertain returns, where uncertainty is represented by interval estimates for the returns, and the minmax regret objective is used. We develop an algorithm that solves this problem in O(min{p,n–p}n) time. This improves the previously known complexity O(min{p,n–p}²n).This research has been supported by the Spanish Science and Technology Ministry and FEDER Grant No. BFM2002-04525-C02-02.Received: October 2002 / Accepted: September 2003