A distributed heuristic solution using arbitration for the MMMKP

The Multiple-Choice Multi-Dimension Multi Knapsack Problem (MMMKP) is the distributed version of Multiple-Choice Multi-Dimension Knapsack Problem (MMKP), a variant of the 0--1 classic Knapsack Problem. Algorithms for finding the exact solution of MMKP as well as MMMKP are not suitable for application in real time decision-making applications. This paper presents a new heuristic algorithm, Arbitrated Heuristic (A-HEU) for solving MMMKP. A-HEU finds the solution with a few messages at the cost of reduced optimality than that of I-HEU, which is a centralized algorithm. We also discuss practical uses of MMMKP such as distributed Video on Demand service.