Restricted robust uniform matroid maximization under interval uncertainty

• 成果类型: Article
• 署名作者: Yaman, H.; Karasan, O. E.; Pinar, M. C.
• 署名单位: Ihsan Dogramaci Bilkent University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0008-1
• 发表日期: 2007
• 页码: 431-441
• 关键词: spanning tree problem; shortest-path problem; bound algorithm; optimization; complexity

摘要

For the problem of selecting p items with interval objective function coefficients so as to maximize total profit, we introduce the r-restricted robust deviation criterion and seek solutions that minimize the r-restricted robust deviation. This new criterion increases the modeling power of the robust deviation (minmax regret) criterion by reducing the level of conservatism of the robust solution. It is shown that r-restricted robust deviation solutions can be computed efficiently. Results of experiments and comparisons with absolute robustness, robust deviation and restricted absolute robustness criteria are reported.