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

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

doi:10.1051/ro/2015061

He, Cheng ¹ ; Leung, Joseph Y-T.² ; Lee, Kangbok ³ ; Pinedo, Michael L.⁴

¹ School of Science, Henan University of Technology, Zhengzhou, Henan 450001, P.R. China.
² Department of Computer Science, New Jersey Institute of Technology, Newark NJ-07102, USA.
³ Department of Business and Economics, York College, The City University of New York, 94-20 Guy R. Brewer Blvd, Jamaica, New York 11451, USA.
⁴ Department of Information, Operations and Management Sciences, Stern School of Business, New York University, 44 West 4th Street, New York 10012-1126, USA.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 995-1001.

Résumé

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 + {(\frac{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$ .

MR Zbl

DOI : 10.1051/ro/2015061

Classification : 68Q25, 90C10, 90C27
Mots clés : Multiple-Choice Knapsack Problem (MCKP), Approximate binary search algorithm, Worst-case performance ratio, Multiple-choice Multi-dimensional Knapsack Problem (MMKP)

Affiliations des auteurs :

He, Cheng ¹ ; Leung, Joseph Y-T. ² ; Lee, Kangbok ³ ; Pinedo, Michael L. ⁴

@article{RO_2016__50_4-5_995_0,
     author = {He, Cheng and Leung, Joseph Y-T. and Lee, Kangbok and Pinedo, Michael L.},
     title = {An improved binary search algorithm for the {Multiple-Choice} {Knapsack} {Problem}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {995--1001},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4-5},
     year = {2016},
     doi = {10.1051/ro/2015061},
     mrnumber = {3570544},
     zbl = {1401.90191},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2015061/}
}

TY  - JOUR
AU  - He, Cheng
AU  - Leung, Joseph Y-T.
AU  - Lee, Kangbok
AU  - Pinedo, Michael L.
TI  - An improved binary search algorithm for the Multiple-Choice Knapsack Problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 995
EP  - 1001
VL  - 50
IS  - 4-5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2015061/
DO  - 10.1051/ro/2015061
LA  - en
ID  - RO_2016__50_4-5_995_0
ER  -

%0 Journal Article
%A He, Cheng
%A Leung, Joseph Y-T.
%A Lee, Kangbok
%A Pinedo, Michael L.
%T An improved binary search algorithm for the Multiple-Choice Knapsack Problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 995-1001
%V 50
%N 4-5
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2015061/
%R 10.1051/ro/2015061
%G en
%F RO_2016__50_4-5_995_0

He, Cheng; Leung, Joseph Y-T.; Lee, Kangbok; Pinedo, Michael L. An improved binary search algorithm for the Multiple-Choice Knapsack Problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 995-1001. doi : 10.1051/ro/2015061. http://archive.numdam.org/articles/10.1051/ro/2015061/

Bibliographie
Cité par

R.D. Armstrong, D.S. Kung, P. Sinha and A.A. Zoltners, A computational study of a multiple-choice knapsack algorithm. ACM Trans. Math. Software 9 (1983) 184–198. | DOI | MR | Zbl

Y. Chen and J.-K. Hao, A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem. Eur. J. Oper. Res. 239 (2014) 313–322. | DOI | MR | Zbl

A.M. Frieze and M.R.B. Clarke, Approximation algorithms for them-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses. Eur. J. Operat. Res. 15 (1984) 100–109. | DOI | MR | Zbl

G. Gens and E. Levner, An approximate binary search algorithm for the multiple-choice knapsack problem. Inf. Process. Lett. 67 (1998) 261–265. | DOI | MR | Zbl

H. Kellerer, U. Pferschy and D. Pisinger, Knapsack problems.Springer (2004). | MR | Zbl

E.L. Lawler, Fast Approximation Algorithms for Knapsack Problems. Math. Oper. Res. 4 (1979) 339–356. | DOI | MR | Zbl

M.J. Magazine and M.-S. Chern, A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. 9 (1984) 244–247. | DOI | MR | Zbl

B. Patt-Shamir and D. Rawitz, Vector bin packing with multiple-choice. Discrete Appl. Math. 160 (2012) 1591–1600. | DOI | MR | Zbl

D. Pisinger, A minimal algorithm for the Multiple-Choice Knapsack Problem. Eur. J. Oper. Res. 83 (1995) 394–410. | DOI | Zbl

Cité par Sources :