An improved algorithm for selecting p items with uncertain returns according to the minmax-regret criterion

• 成果类型: Article
• 署名作者: Conde, E
• 署名单位: University of Sevilla
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0474-7
• 发表日期: 2004
• 页码: 345-353
• 关键词: models

摘要

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}(2)n).