A Computational Study of Approximation Algorithms for a Minmax Resource Allocation Problem

• Autorzy: Bogusz Przybysławski , Adam Kasperski
• Języki publikacji: EN

Abstrakty

EN

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)

Słowa kluczowe

EN

Optimalization; Resource allocation; Algorithms

PL

Optymalizacja; Alokacja zasobów; Algorytmy

• Czasopismo: Operations Research and Decisions
• Rocznik: 2012
• Tom: 22
• Numer: nr 2
• Strony: 35--43

Twórcy

autor

Bogusz Przybysławski

• Wrocław University of Technology

autor

Adam Kasperski

• Wrocław University of Technology

Bibliografia

• [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.

Identyfikatory

DOI

10.5277/ord120203