Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem

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-8542

Full text not available in this repository. Request a copy from the Strathclyde author

Abstract

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.