| Article ID: | iaor20023459 |
| Country: | Poland |
| Volume: | 44 |
| Issue: | 1/2 |
| Start Page Number: | 1 |
| End Page Number: | 23 |
| Publication Date: | Jan 2000 |
| Journal: | Annales Societatis Mathematicae Polonae Series IV Fundamenta Informaticae |
| Authors: | Aho Isto |
| Keywords: | knapsack problem |
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.