Powiadomienia systemowe
- Sesja wygasła!
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
1--23
Opis fizyczny
bibliogr. 23 poz.
Twórcy
autor
- Department of Computer and Information Sciences, P.O. Box 607, FIN-33014 University of Tampere, Finland, tyisah@cs.uta.fi
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS1-0008-0035