
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An Algorithm for the Multidimensional MultipleChoice Knapsack Problem
Martin MOSER Dusan P.JOKANOVIC Norio SHIRATORI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E80A
No.3
pp.582589 Publication Date: 1997/03/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Systems and Control Keyword: realtime configuration, scheduling, knapsack problem, Lagrange multipliers,
Full Text: PDF(633.4KB) >>Buy this Article
Summary:
In this paper we present an algorithm to solve an asyet untreated knapsack problem, the Multidimensional Multiplechoice Knapsack Problem (MMKP). Since our specific application occurs in the realtime domain, a solution for the MMKP with a small upper bound on the runtime is desirable. Thus, the Lagrange multiplier method is chosen, and a heuristic with a worstcase runtime behavior better than O(n^{2}m) is developed, n being the number of elements and m the number of dimensions. Extensive testing against an exact algorithm based on partial enumeration is used to establish the accuracy and efficiency of the heuristic.

