Interactive Knapsacks

Article type: Research Article

Authors: Aho, Isto

Abstract: The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete problems, interactive knapsack heuristic decision problem (IKHD), interactive knapsack decision problem (IKD) and multidimensional cloned knapsack decision problem (MDCS), are presented for the interactive knapsack models. IKD and MDCS are shown to be strongly NP-complete. By using interactive knapsacks we can model many planning and scheduling problems in an innovative way. Possible application areas include electricity management, single and multiprocessor scheduling, and packing and tiling problems. As a by-product we show that the longest weight-constrained path problem is NP-complete.

Keywords: Knapsack problem, knapsack models, longest path, NP-complete

Journal: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 1-23, 2000