Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem Export

@incollection{citeulike:3224554, abstract = {The Multiple-Choice Multi-Dimension Knapsack Problem (MMKP) is a variant of the 0-1 Knapsack Problem, an NP-Hard problem. Hence algorithms for finding the exact solution of MMKP are not suitable for application in real time decision-making applications, like quality adaptation and admission control of an interactive multimedia system. This paper presents two new heuristic algorithms, M-HEU and I-HEU for solving MMKP. Experimental results suggest that M-HEU finds 96\% optimal solutions on average with much reduced computational complexity and performs favorably relative to other heuristic algorithms for MMKP. The scalability property of I-HEU makes this heuristic a strong candidate for use in real time applications.}, author = {Akbar, Md and Manning, Eric and Shoja, Gholamali and Khan, Shahadat}, citeulike-article-id = {3224554}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-45718-6_71}, citeulike-linkout-1 = {http://www.springerlink.com/content/4unc1t2eene1l8yd}, doi = {10.1007/3-540-45718-6_71}, journal = {Computational Science - ICCS 2001}, keywords = {2001, heuristic, mmkp}, pages = {659--668}, posted-at = {2008-09-11 08:30:17}, priority = {2}, title = {Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem}, url = {http://dx.doi.org/10.1007/3-540-45718-6_71}, year = {2001} }

TY - CHAP ID - citeulike:3224554 L3 - citeulike-article-id:3224554 N2 - The Multiple-Choice Multi-Dimension Knapsack Problem (MMKP) is a variant of the 0-1 Knapsack Problem, an NP-Hard problem. Hence algorithms for finding the exact solution of MMKP are not suitable for application in real time decision-making applications, like quality adaptation and admission control of an interactive multimedia system. This paper presents two new heuristic algorithms, M-HEU and I-HEU for solving MMKP. Experimental results suggest that M-HEU finds 96% optimal solutions on average with much reduced computational complexity and performs favorably relative to other heuristic algorithms for MMKP. The scalability property of I-HEU makes this heuristic a strong candidate for use in real time applications. JF - Computational Science - ICCS 2001 EP - 668 TI - Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem SP - 659 KW - 2001 KW - heuristic KW - mmkp AU - Akbar, Md AU - Manning, Eric AU - Shoja, Gholamali AU - Khan, Shahadat PY - 2001/// UR - http://dx.doi.org/10.1007/3-540-45718-6_71 ER -