| Home | Organizers | Proceedings Editors | Proceedings Contributors | Search | | ||
|
|
|||
|
||||
|
|
||||
| Title: | A NEW HEURISTIC ALGORITHM FOR MULTI-DIMENSION MULTIPLE-CHOICE KNAPSACK PROBLEM IN DISTRIBUTED SYSTEM | |
| DOI No: | 10.1142/9781860948534_0006 | |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 50-52) | |
| Author(s): | MD. WASELUL HAQUE SADID
Department of Computer Science & Engineering, Rajshahi University of Engineering & Technology, Bangladesh, India MIRZA NAZRUL ALAM Department of Computer Science & Engineering, Rajshahi University of Engineering & Technology, Bangladesh, India MD. AL MAMUN Department of Computer Science & Engineering, Rajshahi University of Engineering & Technology, Bangladesh, India A. H. M. SARWAR SATTAR Department of Computer Science & Engineering, Rajshahi University of Engineering & Technology, Bangladesh, India MIR MD. JAHANGIR KABIR 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 |
|
| Abstract: | The Multi-Dimension Multiple-Choice Knapsack Problem (MMKP), a variant of the classical 0-1 Knapsack Problem (KP), is an NP-Hard problem and its exact solution is not feasible for real time problems. Therefore heuristic based approximation algorithms are developed for MMKP. The MMKP has a knapsack with a multidimensional capacity constraint and groups of items where each item having a utility value and a multidimensional weight constraint. The problem is to maximize the total value of the items in the knapsack but with the constraint of not exceeding the knapsack capacity. The existing heuristics do not perform better for large number of MMKP data sets. In this paper we proposed a distributed algorithm D-MHEU that achieves approximately 95.5% of the optimal value with much reduced time complexity. | |
| Full Text: | View full text in PDF format (154KB) | |
| TOC: | Back to Table of Contents | |
|
||