Interactive knapsacks

• Autorzy: Aho I.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

knapsack problem; knapsack model; longest path; NP-complete

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2000
• Tom: Vol. 44, Nr 1,2
• Strony: 1--23
• Opis fizyczny: bibliogr. 23 poz.

Twórcy

autor

Aho I.

• Department of Computer and Information Sciences, P.O. Box 607, FIN-33014 University of Tampere, Finland,