An improved binary search algorithm for the Multiple-Choice Knapsack Problem
SCIE
SCOPUS
- Title
- An improved binary search algorithm for the Multiple-Choice Knapsack Problem
- Authors
- Cheng He; Joseph Leung; Lee, K; Micheal Pinedo
- Date Issued
- 2016-10
- Publisher
- EDP Sciences
- Abstract
- The Multiple-Choice Knapsack Problem is defined as a 0-1 Knapsack Problem with additional disjoint multiple-choice constraints. Gens and Levner presented for this problem an approximate binary search algorithm with a worst case ratio of 5. We present an improved approximate binary search algorithm with a ratio of 3 + (1/2)(t) and a running time O(n(t + log m)), where n is the number of items, m the number of classes, and t a positive integer. We then extend our algorithm to make it also applicable to the Multiple-Choice Multidimensional Knapsack Problem with dimension d.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/36721
- DOI
- 10.1051/RO/2015061
- ISSN
- 0399-0559
- Article Type
- Article
- Citation
- RAIRO Operations Research, vol. 50, no. 4-5, page. 995 - 1001, 2016-10
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.