- Autor
- Przybysławski Bogusz (Wrocław University of Technology), Kasperski Adam (Wrocław University of Technology)
- Tytuł
- A Computational Study of Approximation Algorithms for a Minmax Resource Allocation Problem
- Źródło
- Operations Research and Decisions, 2012, vol. 22, no. 2, s. 35-43, tab., bibliogr. 9 poz.
- Słowa kluczowe
- Algorytmy, Optymalizacja, Alokacja zasobów
Algorithms, Optimalization, Resource allocation - Uwagi
- summ.
- Abstrakt
- 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. (original abstract)
- Dostępne w
- Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka SGH im. Profesora Andrzeja Grodka
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Biblioteka Główna Uniwersytetu Ekonomicznego we Wrocławiu - Pełny tekst
- Pokaż
- Bibliografia
-
- AISSI H., BAZGAN C., VANDERPOOTEN D., Min-max and min-max regret versions of combinatorial optimization problems: A survey, European Journal of Operational Research, 2009, 197, 427-438.
- AVERBAKH I., On the complexity of a class of combinatorial optimization problems with uncertainty, Mathematical Programming, 2001, 90, 263-272.
- CONDE E., An improved algorithm for selecting p items with uncertain returns according to the minmax regret criterion, Mathematical Programming, 2004, 100, 345-353.
- IBARAKI T., KATOH N., Resource allocation problems, MIT Press, 1988.
- IIDA H., A note on the max-min 0-1 knapsack problem, Journal of Combinatorial Optimization, 2004, 3, 89-94.
- KASPERSKI A., Discrete optimization with interval data. Minmax regret and fuzzy approach, Studies in Fuzziness and Soft Computing, Vol. 228, Springer, 2008.
- KASPERSKI A., ZIELIŃSKI P., A randomized algorithm for the min-max selecting items problem with uncertain weights, Annals of Operations Research, 2009, 172, 221-230.
- KASPERSKI A., KURPISZ A., ZIELIŃSKI P., Approximating the minmax (regret) selecting items problem, Information Processing Letters, 2013, 113, 23-29.
- KOUVELIS P., YU G., Robust discrete optimization and its applications, Kluwer Academic Publishers, 1997.
- Cytowane przez
- ISSN
- 2081-8858
- Język
- eng
- URI / DOI
- http://dx.doi.org/10.5277/ord120203
