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 条
[31]   The min-max split delivery multi-depot vehicle routing problem with minimum service time requirement [J].
Wang, Xingyin ;
Golden, Bruce ;
Wasil, Edward ;
Zhang, Rui .
COMPUTERS & OPERATIONS RESEARCH, 2016, 71 :110-126
[32]   The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search [J].
Sze, Jeeu Fong ;
Salhi, Said ;
Wassan, Niaz .
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2017, 101 :162-184
[33]   A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem [J].
Sbihi, Abdelkader .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (02) :339-346