BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Przybysławski Bogusz (Wrocław University of Technology), Kasperski Adam (Wrocław University of Technology)
A Computational Study of Approximation Algorithms for a Minmax Resource Allocation Problem
Operations Research and Decisions, 2012, vol. 22, no. 2, s. 35-43, tab., bibliogr. 9 poz.
Słowa kluczowe
Optymalizacja, Alokacja zasobów, Algorytmy
Optimalization, Resource allocation, Algorithms
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 Szkoły Głównej Handlowej w Warszawie
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
  1. 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.
  2. AVERBAKH I., On the complexity of a class of combinatorial optimization problems with uncertainty, Mathematical Programming, 2001, 90, 263-272.
  3. CONDE E., An improved algorithm for selecting p items with uncertain returns according to the minmax regret criterion, Mathematical Programming, 2004, 100, 345-353.
  4. IBARAKI T., KATOH N., Resource allocation problems, MIT Press, 1988.
  5. IIDA H., A note on the max-min 0-1 knapsack problem, Journal of Combinatorial Optimization, 2004, 3, 89-94.
  6. KASPERSKI A., Discrete optimization with interval data. Minmax regret and fuzzy approach, Studies in Fuzziness and Soft Computing, Vol. 228, Springer, 2008.
  7. 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.
  8. KASPERSKI A., KURPISZ A., ZIELIŃSKI P., Approximating the minmax (regret) selecting items problem, Information Processing Letters, 2013, 113, 23-29.
  9. KOUVELIS P., YU G., Robust discrete optimization and its applications, Kluwer Academic Publishers, 1997.
Cytowane przez
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu