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 条
12345