- Tytuł:
- A computational study of approximation algorithms for a minmax resource allocation problem
- Autorzy:
-
Przybysławski, B.
Kasperski, A. - Powiązania:
- https://bibliotekanauki.pl/articles/406619.pdf
- Data publikacji:
- 2012
- Wydawca:
- Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
- Tematy:
-
discrete optimization
robust optimization
resource allocation
approximation algorithms - Opis:
- A basic resource allocation problem with uncertain costs has been discussed. The problem is to minimize the total cost of choosing exactly p items out of n available. The uncertain item costs are specified as a discrete scenario set and the minmax criterion is used to choose a solution. This problem is known to be NP-hard, but several approximation algorithms exist. The aim of this paper is to investigate the quality of the solutions returned by these approximation algorithms. According to the results obtained, the randomized algorithms described are fast and output solutions of good quality, even if the problem size is large.
- Źródło:
-
Operations Research and Decisions; 2012, 22, 2; 35-43
2081-8858
2391-6060 - Pojawia się w:
- Operations Research and Decisions
- Dostawca treści:
- Biblioteka Nauki
Artykuł