| Home | Organizers | Proceedings Editors | Proceedings Contributors | Search | | ||
|
|
|||
|
||||
|
|
||||
| Title: | A NEW STRATEGY FOR SOLVING MULTIPLE-CHOICE MULTIPLE-DIMENSION KNAPSACK PROBLEM IN PRAM MODEL | |
| DOI No: | 10.1142/9781860948534_0009 | |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 63-67) | |
| Author(s): | MD. WASELUL HAQUE SADID
Department of Computer Science & Engineering, Rajshahi University of Engineering & Technology, Bangladesh, India MD. RABIUL ISLAM Department of Computer Science & Engineering, Rajshahi University of Engineering & Technology, Bangladesh, India S. M. KAMRUL HASAN Department of Computer Science & Engineering, Rajshahi University of Engineering & Technology, Bangladesh, India MD. MOSTOFA AKBAR Department of Computer Science and Engineering, University of Engineering and Technology, Bangladesh, India |
|
| Abstract: | This paper presents a new heuristic algorithm for the Multiple-Choice Multi-Dimension Knapsack Problem (MMKP) in PRAM model. MMKP is a variant of the classical 0-1 knapsack problem, has a knapsack with multidimensional capacity constraints, groups of items, each item having a utility value and multidimensional resource constraints. The problem is to maximize the total value of the items in the knapsack with the constraint of not exceeding the knapsack capacity. Since MMKP is an NP-Hard problem, its exact solution is not suitable for real time problems, so heuristic based approximation algorithms are developed. We present a parallel heuristic algorithm here that runs in O(log nl(log n + log m + log log l)) time in CRCW PRAM machine; taking O(n log n(log n + ml)) operations. Experimental results show that it achieves 95% optimal solution on average. | |
| Full Text: | View full text in PDF format (246KB) | |
| TOC: | Back to Table of Contents | |
|
||