An improved binary search algorithm for the Multiple-Choice Knapsack Problem

DOI10.1051/ro/2015061zbMath1401.90191OpenAlexW2540476875MaRDI QIDQ2954365

Kangbok Lee, Cheng He, Joseph Y.-T. Leung, Michael L. Pinedo

Publication date: 12 January 2017

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ro/2015061

zbMATH Keywords

worst-case performance ratioapproximate binary search algorithmmultiple-choice knapsack problem (MCKP)multiple-choice multi-dimensional knapsack problem (MMKP)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• An approximate binary search algorithm for the multiple-choice knapsack problem
• A ``reduce and solve approach for the multiple-choice multidimensional knapsack problem
• Vector bin packing with multiple-choice
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• A minimal algorithm for the multiple-choice knapsack problem
• A computational study of a multiple-choice knapsack algorithm
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• Fast Approximation Algorithms for Knapsack Problems

This page was built for publication: An improved binary search algorithm for the Multiple-Choice Knapsack Problem