共 33 条
A randomized algorithm for the min-max selecting items problem with uncertain weights
被引:11
作者:
Kasperski, Adam
[1
]
Zielinski, Pawel
[2
]
机构:
[1] Wroclaw Univ Technol, Inst Ind Engn & Management, PL-50370 Wroclaw, Poland
[2] Wroclaw Univ Technol, Inst Math & Comp Sci, PL-50370 Wroclaw, Poland
关键词:
Minmax;
Selecting items;
Randomized algorithm;
Robust optimization;
COMBINATORIAL OPTIMIZATION PROBLEMS;
REGRET VERSIONS;
D O I:
10.1007/s10479-009-0564-x
中图分类号:
C93 [管理学];
O22 [运筹学];
学科分类号:
070105 ;
12 ;
1201 ;
1202 ;
120202 ;
摘要:
This paper deals with the min-max version of the problem of selecting p items of the minimum total weight out of a set of n items, where the item weights are uncertain. The discrete scenario representation of uncertainty is considered. The Computational complexity of the problem is explored. A randomized algorithm for the problem is then proposed, which returns an O(ln K)-approximate Solution with a high probability, where K is the number of scenarios. This is the first approximation algorithm with better than K worst case ratio for the class of min-max combinatorial optimization problems with unbounded scenario set.
引用
收藏
页码:221 / 230
页数:10
相关论文
共 33 条