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 条
  • [21] DGSA: discrete gravitational search algorithm for solving knapsack problem
    Hedieh Sajedi
    Seyedeh Fatemeh Razavi
    Operational Research, 2017, 17 : 563 - 591
  • [22] A surface-based DNA algorithm for the solving binary knapsack problem
    Darehmiraki, Majid
    Nehi, Hasan Mishmast
    APPLIED MATHEMATICS AND COMPUTATION, 2007, 188 (02) : 1991 - 1994
  • [23] New binary bat algorithm for solving 0–1 knapsack problem
    Rizk M. Rizk-Allah
    Aboul Ella Hassanien
    Complex & Intelligent Systems, 2018, 4 : 31 - 53
  • [24] Novel Binary Biogeography-Based Optimization Algorithm for the Knapsack Problem
    Zhao, Bingyan
    Deng, Changshou
    Yang, Yanling
    Peng, Hu
    ADVANCES IN SWARM INTELLIGENCE, ICSI 2012, PT I, 2012, 7331 : 217 - 224
  • [25] Binary Mother Tree Optimization Algorithm for 0/1 Knapsack Problem
    Korani, Wael
    NEURAL INFORMATION PROCESSING, ICONIP 2023, PT I, 2024, 14447 : 201 - 213
  • [26] A Binary Differential Evolution with Adaptive Parameters Applied to the Multiple Knapsack Problem
    Andre, Leanderson
    Parpinelli, Rafael Stubs
    NATURE-INSPIRED COMPUTATION AND MACHINE LEARNING, PT II, 2014, 8857 : 61 - 71
  • [27] A Novel Hybrid Tabu Search Algorithm With Binary Differential Operator for Knapsack Problems
    Hu, Jun
    Zhang, Qingfu
    Jiao, Yong-Chang
    2020 16TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND SECURITY (CIS 2020), 2020, : 259 - 263
  • [28] Hybrid Ant Colony Optimization Algorithm for Multiple Knapsack Problem
    Fidanova, Stefka
    2020 5TH IEEE INTERNATIONAL CONFERENCE ON RECENT ADVANCES AND INNOVATIONS IN ENGINEERING (IEEE - ICRAIE-2020), 2020,
  • [29] A new grouping genetic algorithm for the quadratic multiple knapsack problem
    Singh, Alok
    Baghel, Anurag Singh
    EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 2007, 4446 : 210 - +
  • [30] PROBABILISTIC TABU SEARCH WITH MULTIPLE NEIGHBORHOODS FOR THE DISJUNCTIVELY CONSTRAINED KNAPSACK PROBLEM
    Ben Salem, Mariem
    Hanafi, Said
    Taktak, Raouia
    Ben Abdallah, Hanene
    RAIRO-OPERATIONS RESEARCH, 2017, 51 (03) : 627 - 637
12345