Shahriar, A.Z.M. and Akbar, M.M. and Rahman, M.S. and Newton, M.A.H. (2008) A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem. Journal of Supercomputing, 43 (3). pp. 257-280. ISSN 0920-8542Full text not available in this repository. (Request a copy from the Strathclyde author)
This paper presents a multiprocessor based heuristic algorithm for the Multi-dimensional Multiple Choice Knapsack Problem (MMKP). MMKP is a variant of the classical 0-1 knapsack problem, where items having a value and a number of resource requirements are divided into groups. Exactly one item has to be picked up from each group to achieve a maximum total value without exceeding the resource constraint of each type. MMKP has many real world applications including admission control in adaptive multimedia server system. Exact solution to this problem is NP-Hard, and hence is not feasible for real time applications like admission control. Therefore, heuristic solutions have been developed to solve the MMKP. M-HEU is one such heuristic, which solves the MMKP achieving a reasonable percentage of optimality. In this paper, we present a multiprocessor algorithm based on M-HEU, which runs in O(T/p+s(p)) time, where T is the time required by the algorithm using single processor, p is the number of processors and s(p), a function of p, is the synchronization overhead. We also present the worst-case analysis of our algorithm, the computation of the optimal number of processors as well as the lower bound of the total value that can be achieved by the heuristic.
|Keywords:||knapsack problem, heuristic algorithms, process synchronization, inter process communication, multiprocessor systems, Electronic computers. Computer science, Hardware and Architecture, Theoretical Computer Science, Software, Information Systems|
|Subjects:||Science > Mathematics > Electronic computers. Computer science|
|Department:||Faculty of Science > Computer and Information Sciences|
|Depositing user:||Strathprints Administrator|
|Date Deposited:||01 Jun 2010 11:51|
|Last modified:||04 May 2016 15:09|