Title of article :
Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls
Author/Authors :
Md Mostofa Akbar، نويسنده , , M. Sohel Rahman، نويسنده , , M. Kaykobad، نويسنده , , E.G. Manning، نويسنده , , G.C. Shoja، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 2006
Pages :
15
From page :
1259
To page :
1273
Abstract :
This paper presents a heuristic to solve the Multidimensional Multiple-choice Knapsack Problem (MMKP), a variant of the classical 0–1 Knapsack Problem. We apply a transformation technique to map the multidimensional resource consumption to single dimension. Convex hulls are constructed to reduce the search space to find the near-optimal solution of the MMKP. We present the computational complexity of solving the MMKP using this approach. A comparative analysis of different heuristics for solving the MMKP has been presented based on the experimental results.
Keywords :
Convex hull , Heuristics , Multimedia systems , Algorithms , MMKP
Journal title :
Computers and Operations Research
Serial Year :
2006
Journal title :
Computers and Operations Research
Record number :
928705
Link To Document :
بازگشت