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

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)995-1001
Number of pages7
JournalRAIRO - Operations Research
Volume50
Issue number4-5
DOIs
StatePublished - Oct 1 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Approximate binary search algorithm
  • Multiple-Choice Knapsack Problem (MCKP)
  • Multiple-choice Multi-dimensional Knapsack Problem (MMKP)
  • Worst-case performance ratio

Fingerprint

Dive into the research topics of 'An improved binary search algorithm for the Multiple-Choice Knapsack Problem'. Together they form a unique fingerprint.

Cite this