An approximate binary search algorithm for the multiple-choice knapsack problem

被引：12
作者：
Gens, G
Levner, E
机构：
[1] Ctr Technol Educ, Dept Comp Sci, IL-58102 Holon, Israel
[2] Inst Automat, Moscow, Russia
来源：
INFORMATION PROCESSING LETTERS | 1998年 / 67卷 / 05期
关键词：
knapsack problem; approximate algorithms; approximate binary search; algorithms;
D O I：
10.1016/S0020-0190(98)00115-X
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A fast approximation algorithm for the multiple-choice knapsack problem is proposed whose solution is guaranteed to be 4/5-bounded. The algorithm is based on binary search and runs in O(n log m) time, n being the total number of items and m the number of multiple-choice classes in the knapsack problem. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：261 / 265
页数：5
相关论文
共 50 条
[31]   New binary bat algorithm for solving 0-1 knapsack problem [J].
Rizk-Allah, Rizk M. ;
Hassanien, Aboul Ella .
COMPLEX & INTELLIGENT SYSTEMS, 2018, 4 (01) :31-53
[32]   The binary knapsack problem with qualitative levels [J].
Schaefer, Luca E. ;
Dietz, Tobias ;
Barbati, Maria ;
Figueira, Jose Rui ;
Greco, Salvatore ;
Ruzika, Stefan .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 289 (02) :508-514
[33]   Experimental evaluation of some approximate algorithms of solving multidimensional knapsack problem [J].
Yuhimenko, Birute I. ;
Kornilova, Svitlana V. ;
Asaulyuk, Inna O. ;
Kisala, Piotr ;
Luganskaya, Saule ;
Shedreyeva, Indira .
OPTICAL FIBERS AND THEIR APPLICATIONS 2018, 2019, 11045
[34]   Vector bin packing with multiple-choice [J].
Patt-Shamir, Boaz ;
Rawitz, Dror .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (10-11) :1591-1600
[35]   Vector Bin Packing with Multiple-Choice [J].
Patt-Shamir, Boaz ;
Rawitz, Dror .
ALGORITHM THEORY - SWAT 2010, PROCEEDINGS, 2010, 6139 :248-259
[36]   Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem [J].
Francois Vanderbeck .
Mathematical Programming, 2002, 94 :125-136
[37]   Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm [J].
Gherboudj, Amira ;
Layeb, Abdesslem ;
Chikhi, Salim .
INTERNATIONAL JOURNAL OF BIO-INSPIRED COMPUTATION, 2012, 4 (04) :229-236
[38]   Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem [J].
Vanderbeck, F .
MATHEMATICAL PROGRAMMING, 2002, 94 (01) :125-136
[39]   Cognitive discrete gravitational search algorithm for solving 0-1 knapsack problem [J].
Razavi, Seyedeh Fatemeh ;
Sajedi, Hedieh .
JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2015, 29 (05) :2247-2258
[40]   Evolution of new algorithms for the binary knapsack problem [J].
Parada, Lucas ;
Herrera, Carlos ;
Sepulveda, Mauricio ;
Parada, Victor .
NATURAL COMPUTING, 2016, 15 (01) :181-193
12345