Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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.

Item type: Article
ID code: 19831
Keywords: knapsack problem, heuristic algorithms, process synchronization, inter process communication, multiprocessor systems, Electronic computers. Computer science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Unknown Department
Related URLs:
    Depositing user: Strathprints Administrator
    Date Deposited: 01 Jun 2010 12:51
    Last modified: 08 Sep 2011 16:05
    URI: http://strathprints.strath.ac.uk/id/eprint/19831

    Actions (login required)

    View Item