Heurystyczne algorytmy ograniczonej alokacji zasobu

• Autorzy: Pieńkosz K.

Warianty tytułu

EN

Heuristic algorithms for the cardinality constrained knapsack problem

• Języki publikacji: PL

Abstrakty

PL

W komórkach żywych organizmów zachodzi wiele procesów biochemicznych podlegających skomplikowanym mechanizmom regulacji. Jednym z nich jest proces produkcji cząsteczek mRNA, zachodzący w jądrze komórkowym. Z praktycznego punktu widzenia jest to proces dyskretny. W niektórych przypadkach może być on jednak opisywany modelami ciągłymi. W niniejszej pracy pokazane są warunki, w jakich zarówno opis dyskretny, jak i ciągły prowadzą do takich samych jakościowo wyników.

EN

In the paper a variant of the continuous knapsack problem is considered in which no more than a specified number of variables are allowed to be positive. Two heuristic algorithms are proposed to solve the problem. Some results of the worst-case performance analysis for these algorithms are provided.

Słowa kluczowe

PL

alokacja zasobów; problem plecakowy; algorytmy heurystyczne; oszacowania dokładności algorytmów

EN

resorce allocation; knapsack problem; heuristic algorithms; worst-case analysis

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2008
• Tom: R. 84, nr 9
• Strony: 89--92
• Opis fizyczny: Bibliogr. 6 poz., rys., wykr.

Twórcy

autor

Pieńkosz K.

• Politechnika Warszawska, Instytut Automatyki i Informatyki Stosowanej,

Bibliografia

• [1] Caprara A., Kellerer H., Pferschy U., Pisinger D., Approximation algorithms for knapsack problems with cardinality constraints, European Journal of Operational Research, 123 (2000), 333-345
• [2] de Farias I.R. Jr, Nemhauser G.L, A polyhedral study of the cardinality constrained knapsack problem, Mathematical Programming, Ser. A 96 (2003), 439-467
• [3] Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer, Berlin (2004)
• [4] Mareollo S., Toth P., Knapsack Problems, Algorithms and Computer Implementations, John Wiley and Sons, New York (1990)
• [5] Martello S., Toth P., Upper bounds and algorithms for hard 0-1 knapsack problems, Operations Research, 45 (1997), 768-778
• [6] Pieńkosz K., On solving the semi-continuous knapsack problem, Proc. of the 11th IEEE International Conference on Methods and Models in Automation and Robotics, (2005), 851-855