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 language | English (US) |
|---|---|
| Pages (from-to) | 995-1001 |
| Number of pages | 7 |
| Journal | RAIRO - Operations Research |
| Volume | 50 |
| Issue number | 4-5 |
| DOIs | |
| State | Published - 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